Skip to content

Commit bc1be2c

Browse files
authored
perf: stop dictionary work growing with the group count (apache#26703)
## Which issue does this PR close? - Closes apache#26696. ## Rationale for this change Queries that group on a high-cardinality dictionary column slow down as the group count grows. On ClickBench `hits_partitioned` with `enable_rle_to_dictionary = true`, this PR takes the suite from 78.8 s to 42.8 s, with Q33 and Q34 about 3.5x faster and peak memory slightly lower ([bot run](apache#26703 (comment))). A hash aggregate builds its output once and emits it in `batch_size` slices, and slicing a `DictionaryArray` keeps every value. Every slice therefore carries every group's value, so hashing, functions such as `lower`, the repartition coalescer and the final aggregate do work per slice that grows with the group count. ## What changes are included in this PR? Start reading at `next_batch` in `aggregates/aggregate_hash_table/common.rs`. - **Aggregate output, the main gain.** A slice with more values than rows now holds only the values its rows reference. No threshold is needed: each group is emitted once, so the cost is fixed per group. - **A bound for other batches.** Filters and scans also keep whole dictionaries, so `hash_dictionary` and the new `map_dictionary_values` handle at most `MAX_DICTIONARY_VALUES_PER_ROW` (64) values per row and compact past that. Too high only gives up an improvement, while too low makes cheap work slower: `lower` and `upper` break even at about 40 values per row with keys in random order. The filter and scan queries I measured showed no visible difference, so this is a guard, not a measured speedup. - **`compact_dictionary`** does both, taking each referenced value once. `take(values, keys)` copies per row, and multi-column group keys repeat dictionary keys, so it can overflow `i32` offsets, need more rows than the key type holds, and copy a long value thousands of times. - **`map_dictionary_values`** replaces `dictionary.with_values(f(values))` in the string functions, Spark `hex`, `array_agg`, `regexp_replace` and `substr`, and `clippy.toml` disallows calling `with_values` directly. If `f` fails, it retries on only the referenced values, because `f` can see values no row references. This replaces `substr`'s own fallback. Each aggregate slice now has its own values `Arc`, so the hash cache proposed in apache#26816 would miss on these slices. The two haven't been measured together. ## Benchmarks | ClickBench partitioned | main | this PR | |---|---|---| | Total | 78.8 s | 42.8 s | | Q33 | 14.9 s | 4.4 s | | Q34 | 14.8 s | 4.1 s | | Q18 | 7.6 s | 2.3 s | | Peak memory | 13.1 GiB | 12.7 GiB | Q35, Q32 and Q40 read 1.05x to 1.10x slower by minimum. None groups on a dictionary column, so this PR only adds a type check per output batch for them, and the bot's noise is about 5-7% per query. <details><summary>Local runs on a busy 12-core laptop: `lower`, memory limits, filter queries</summary> Results were identical on every query. Treat small differences as noise. `lower` over a dictionary GROUP BY, which ClickBench doesn't cover: ```sql SELECT lower(s), c FROM ( SELECT "SearchPhrase" s, COUNT(*) c FROM hits WHERE "SearchPhrase" <> '' GROUP BY s ) ORDER BY c DESC, 1 LIMIT 10; ``` | partitions | 12 | 24 | 32 | 48 | 64 | |---|---|---|---|---|---| | ratio to main | 0.08x | 0.14x | 0.16x | 0.24x | 0.22x | Q33 under `--memory-limit`, one run each: | limit | main | this PR | |---|---|---| | 12g | fails: TopK resources exhausted | 6.3 s | | 8g | 23.6 s | 16.4 s | | 6g | 31.2 s | 19.4 s | | 4g | 20.2 s | 14.3 s | Filter and scan queries using `reverse`, `initcap`, `LIKE` and hashing after a filter, with the bound at 40: 0.94x to 1.05x of main. </details> ## What is the testing strategy for this PR? - `dictionary.slt` compares each function on aggregate output and on filter output with the same function on the decoded value. The comparison is projected, because a filter on the group key is pushed below the aggregate. - Unit tests cover `next_batch`, `map_dictionary_values` and hashing: repeated keys, NULL groups, more rows than the key type holds, and a value too long to copy per row. - The `dictionary_sliced` case in `datafusion/common/benches/with_hashes.rs` covers 8 and 128 values per row. ## Are there any user-facing changes? No behavior changes. `datafusion_common::utils` gains `compact_dictionary`, `map_dictionary_values` and `MAX_DICTIONARY_VALUES_PER_ROW`.
1 parent 4bf32cb commit bc1be2c

21 files changed

Lines changed: 683 additions & 123 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎clippy.toml‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@
55
disallowed-methods = [
66
{ path = "tokio::task::spawn", reason = "To provide cancel-safety, use `SpawnedTask::spawn` instead (https://github.com/apache/datafusion/issues/6513)" },
77
{ path = "tokio::task::spawn_blocking", reason = "To provide cancel-safety, use `SpawnedTask::spawn_blocking` instead (https://github.com/apache/datafusion/issues/6513)" },
8+
{ path = "arrow_array::array::AnyDictionaryArray::with_values", reason = "Running code on every dictionary value can cost far more than the batch has rows; use `datafusion_common::utils::map_dictionary_values`" },
9+
{ path = "arrow_array::array::DictionaryArray::with_values", reason = "Running code on every dictionary value can cost far more than the batch has rows; use `datafusion_common::utils::map_dictionary_values`" },
810
{ path = "std::vec::Vec::reserve", reason = "Use `Vec::try_reserve` so allocation failures can be reported instead of panicking", replacement = "try_reserve" },
911
]
1012

‎datafusion/common/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +59,7 @@ name = "record_batch_memory"
5959
arrow = { workspace = true }
6060
arrow-ipc = { workspace = true }
6161
arrow-schema = { workspace = true, features = ["canonical_extension_types"] }
62+
arrow-select = { workspace = true }
6263
chrono = { workspace = true }
6364
foldhash = "0.2"
6465
half = { workspace = true }

‎datafusion/common/benches/with_hashes.rs‎

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
use arrow::array::{
88
Array, ArrayRef, ArrowPrimitiveType, DictionaryArray, FixedSizeListArray,
99
GenericStringArray, Int32Array, Int64Array, ListArray, ListViewArray, MapArray,
10-
NullArray, NullBufferBuilder, OffsetSizeTrait, PrimitiveArray, RunArray,
10+
NullArray, NullBufferBuilder, OffsetSizeTrait, PrimitiveArray, RunArray, StringArray,
1111
StringViewArray, StructArray, UnionArray, make_array,
1212
};
1313
use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer};
@@ -394,6 +394,22 @@ fn sliced_array_benchmark(c: &mut Criterion) {
394394
);
395395
}
396396
}
397+
398+
// Sliced DictionaryArray with one value per row of the full array, like the
399+
// group keys an aggregation emits in `batch_size` slices. Hashing reduces
400+
// it to the referenced values only above 64 values per row, so 1/8 keeps
401+
// the full dictionary and 1/128 doesn't.
402+
for ratio in [8, 128] {
403+
let total_rows = BATCH_SIZE * ratio;
404+
let full_array = distinct_dictionary_array(total_rows);
405+
let sliced = full_array.slice(BATCH_SIZE * (ratio / 2), BATCH_SIZE);
406+
c.bench_function(
407+
&format!("dictionary_sliced: 1/{ratio} of {total_rows} values"),
408+
|b| {
409+
do_hash_test_with_len(b, std::slice::from_ref(&sliced), BATCH_SIZE);
410+
},
411+
);
412+
}
397413
}
398414

399415
fn do_hash_test_with_len(b: &mut Bencher, arrays: &[ArrayRef], expected_len: usize) {
@@ -407,6 +423,14 @@ fn do_hash_test_with_len(b: &mut Bencher, arrays: &[ArrayRef], expected_len: usi
407423
});
408424
}
409425

426+
/// A `Dictionary(Int32, Utf8)` with a distinct value for every row
427+
fn distinct_dictionary_array(num_rows: usize) -> ArrayRef {
428+
let values =
429+
StringArray::from_iter_values((0..num_rows).map(|i| format!("group_{i}")));
430+
let keys = Int32Array::from_iter_values(0..num_rows as i32);
431+
Arc::new(DictionaryArray::<Int32Type>::try_new(keys, Arc::new(values)).unwrap())
432+
}
433+
410434
fn list_array(num_rows: usize) -> ArrayRef {
411435
let mut rng = make_rng();
412436
let elements_per_row = 5;

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 94 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44

55
//! Functionality used both on logical and physical plans
66
7+
#[cfg(not(feature = "force_hash_collisions"))]
8+
use crate::utils::compact_oversized_dictionary;
79
use arrow::array::types::{IntervalDayTime, IntervalMonthDayNano};
810
use arrow::array::*;
911
#[cfg(not(feature = "force_hash_collisions"))]
@@ -656,7 +658,11 @@ fn hash_dictionary<K: ArrowDictionaryKeyType>(
656658
) -> Result<()> {
657659
// Hash each dictionary value once, and then use that computed
658660
// hash for each key value to avoid a potentially expensive
659-
// redundant hashing for large dictionary elements (e.g. strings)
661+
// redundant hashing for large dictionary elements (e.g. strings).
662+
// A dictionary with many more values than rows (e.g. a slice) is first
663+
// reduced to the values its rows reference.
664+
let compacted = compact_oversized_dictionary(array)?;
665+
let array = compacted.as_ref().unwrap_or(array);
660666
let dict_values = array.values();
661667
let mut dict_hashes = vec![0; dict_values.len()];
662668
create_hashes([dict_values], random_state, &mut dict_hashes)?;
@@ -671,6 +677,8 @@ fn hash_dictionary_with_child_hashing<K: ArrowDictionaryKeyType>(
671677
hashes_buffer: &mut [u64],
672678
multi_col: bool,
673679
) -> Result<()> {
680+
let compacted = compact_oversized_dictionary(array)?;
681+
let array = compacted.as_ref().unwrap_or(array);
674682
let dict_values = array.values();
675683
let mut dict_hashes = vec![0; dict_values.len()];
676684
child_hashing.create_hashes([dict_values], &mut dict_hashes)?;
@@ -1836,6 +1844,91 @@ mod tests {
18361844
assert_ne!(dict_hashes[0], dict_hashes[2]);
18371845
}
18381846

1847+
#[test]
1848+
// Tests actual values of hashes, which are different if forcing collisions
1849+
#[cfg(not(feature = "force_hash_collisions"))]
1850+
fn create_hashes_for_dict_with_more_rows_than_the_key_type_holds() {
1851+
fn check<K: ArrowDictionaryKeyType>(distinct_keys: usize) {
1852+
let values: ArrayRef = Arc::new(StringArray::from_iter_values(
1853+
(0..20_000).map(|i| format!("v{i}")),
1854+
));
1855+
let keys: ScalarBuffer<K::Native> = (0..300)
1856+
.map(|i| K::Native::usize_as(i % distinct_keys))
1857+
.collect();
1858+
let keys = PrimitiveArray::<K>::new(keys, None);
1859+
let dict: ArrayRef =
1860+
Arc::new(DictionaryArray::try_new(keys, values).unwrap());
1861+
let decoded = arrow::compute::cast(&dict, &DataType::Utf8).unwrap();
1862+
let random_state = RandomState::with_seed(0);
1863+
1864+
let mut dict_hashes = vec![0; dict.len()];
1865+
create_hashes([&dict], &random_state, &mut dict_hashes).unwrap();
1866+
let mut decoded_hashes = vec![0; dict.len()];
1867+
create_hashes([&decoded], &random_state, &mut decoded_hashes).unwrap();
1868+
assert_eq!(dict_hashes, decoded_hashes);
1869+
}
1870+
check::<UInt8Type>(250);
1871+
check::<Int8Type>(120);
1872+
}
1873+
1874+
#[test]
1875+
// Tests actual values of hashes, which are different if forcing collisions
1876+
#[cfg(not(feature = "force_hash_collisions"))]
1877+
fn create_hashes_for_dict_does_not_copy_a_value_per_row() {
1878+
// 64 copies of this value wouldn't fit in `i32` offsets
1879+
let long = "x".repeat(34 * 1024 * 1024);
1880+
let values: ArrayRef = Arc::new(StringArray::from_iter_values(
1881+
(0..5000).map(|i| if i == 0 { long.as_str() } else { "short" }),
1882+
));
1883+
let dict: ArrayRef = Arc::new(
1884+
DictionaryArray::try_new(Int32Array::from(vec![0; 64]), values).unwrap(),
1885+
);
1886+
let single: ArrayRef = Arc::new(StringArray::from(vec![long.as_str()]));
1887+
let random_state = RandomState::with_seed(0);
1888+
1889+
let mut dict_hashes = vec![0; dict.len()];
1890+
create_hashes([&dict], &random_state, &mut dict_hashes).unwrap();
1891+
let mut single_hash = vec![0; 1];
1892+
create_hashes([&single], &random_state, &mut single_hash).unwrap();
1893+
assert_eq!(dict_hashes, vec![single_hash[0]; 64]);
1894+
}
1895+
1896+
#[test]
1897+
// Tests actual values of hashes, which are different if forcing collisions
1898+
#[cfg(not(feature = "force_hash_collisions"))]
1899+
fn create_hashes_for_dict_slices_with_more_values_than_rows() {
1900+
use crate::utils::MAX_DICTIONARY_VALUES_PER_ROW;
1901+
1902+
let values: ArrayRef = Arc::new(StringArray::from_iter(
1903+
(0..200).map(|i| (i != 2).then(|| format!("v{i}"))),
1904+
));
1905+
let keys = Int8Array::from_iter((0..48).map(|i| (i % 7 != 1).then_some(i)));
1906+
let dict: ArrayRef = Arc::new(DictionaryArray::try_new(keys, values).unwrap());
1907+
let ints: ArrayRef = Arc::new(Int32Array::from_iter_values(0..48));
1908+
let random_state = RandomState::with_seed(0);
1909+
1910+
let mut single = vec![0; dict.len()];
1911+
create_hashes([&dict], &random_state, &mut single).unwrap();
1912+
let mut multi = vec![0; dict.len()];
1913+
create_hashes([&ints, &dict], &random_state, &mut multi).unwrap();
1914+
1915+
for (offset, len) in [(0, 2), (1, 2), (8, 1), (46, 2)] {
1916+
let slice = dict.slice(offset, len);
1917+
assert!(
1918+
slice.as_any_dictionary().values().len()
1919+
> MAX_DICTIONARY_VALUES_PER_ROW * len
1920+
);
1921+
let mut hashes = vec![0; len];
1922+
create_hashes([&slice], &random_state, &mut hashes).unwrap();
1923+
assert_eq!(hashes, single[offset..offset + len]);
1924+
1925+
let ints = ints.slice(offset, len);
1926+
let mut hashes = vec![0; len];
1927+
create_hashes([&ints, &slice], &random_state, &mut hashes).unwrap();
1928+
assert_eq!(hashes, multi[offset..offset + len]);
1929+
}
1930+
}
1931+
18391932
#[test]
18401933
// Tests actual values of hashes, which are different if forcing collisions
18411934
#[cfg(not(feature = "force_hash_collisions"))]

0 commit comments

Comments
 (0)