Skip to content

Commit 6357574

Browse files
adriangbclaude
andcommitted
perf: dedupe collapsed hash join IN lists and add combined bounds
The per-partition InList arrays hold one entry per build row, and the collapsed union concatenated them. On TPC-DS SF1 with 12 partitions, Q65 pushed 54,000 entries for 6 distinct keys, and Q18 pushed 10,848 entries for 1,178 distinct keys. The pruning code uses an IN list only up to `max_in_list_size` (20) entries, so these filters gave no pruning term, and the long lists made the statistics evaluation for each file range slow. The union is now deduplicated and sorted with the arrow row format before the IN list is built. This works for single and struct (multi-column) keys and dictionaries, keeps one NULL, and makes the list order deterministic. The 1 MiB cap now applies to the deduplicated union. The collapsed filter also gets one range per key column, `col >= min AND col <= max`, from the combined bounds of all non-empty partitions, before the IN list. Every key in the union is inside this range, so the filter stays exact, and the pruning code can use the range when the list has more than `max_in_list_size` entries. Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 3eb7cf7 commit 6357574

4 files changed

Lines changed: 349 additions & 29 deletions

File tree

‎datafusion/core/tests/physical_optimizer/filter_pushdown.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1165,7 +1165,7 @@ async fn test_hashjoin_dynamic_filter_pushdown_partitioned() {
11651165
- RepartitionExec: partitioning=Hash([a@0, b@1], 12), input_partitions=1
11661166
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
11671167
- RepartitionExec: partitioning=Hash([a@0, b@1], 12), input_partitions=1
1168-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, e], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ struct(a@0, b@1) IN (SET) ([{c0:ab,c1:bb}, {c0:aa,c1:ba}]) ]
1168+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, e], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ a@0 >= aa AND a@0 <= ab AND b@1 >= ba AND b@1 <= bb AND struct(a@0, b@1) IN (SET) ([{c0:aa,c1:ba}, {c0:ab,c1:bb}]) ]
11691169
"
11701170
);
11711171

‎datafusion/physical-plan/src/joins/hash_join/inlist_builder.rs‎

Lines changed: 67 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,10 +17,13 @@
1717

1818
//! Utilities for building InList expressions from hash join build side data
1919
20+
use std::collections::HashSet;
2021
use std::sync::Arc;
2122

22-
use arrow::array::{ArrayRef, StructArray};
23+
use arrow::array::{ArrayRef, StructArray, UInt64Array};
24+
use arrow::compute::take;
2325
use arrow::datatypes::{Field, FieldRef, Fields};
26+
use arrow::row::{Row, RowConverter, SortField};
2427
use arrow_schema::DataType;
2528
use datafusion_common::Result;
2629

@@ -77,6 +80,48 @@ pub(super) fn build_struct_inlist_values(
7780
Ok(Some(source_array))
7881
}
7982

83+
/// Removes duplicate entries from an `IN` list value array and sorts the
84+
/// remaining entries.
85+
///
86+
/// Equality and order are those of the arrow row format produced by
87+
/// [`RowConverter`] with default [`SortField`] options (ascending, NULLs
88+
/// first). This works for single values, for the struct values of
89+
/// multi-column keys and for dictionaries. NULLs compare equal to each other,
90+
/// so many NULLs collapse into one NULL. That does not change the result of
91+
/// `IN`: one NULL in the list gives the same three-valued result as many.
92+
///
93+
/// Sorting makes the list independent of the order in which build rows
94+
/// arrive, so the displayed filter is deterministic.
95+
///
96+
/// Returns the input unchanged when it has fewer than two entries, or when
97+
/// its type cannot be row-encoded (deduplication is an optimization, not a
98+
/// requirement).
99+
pub(super) fn sorted_distinct_inlist_values(values: ArrayRef) -> Result<ArrayRef> {
100+
if values.len() < 2 {
101+
return Ok(values);
102+
}
103+
104+
let sort_field = SortField::new(values.data_type().clone());
105+
if !RowConverter::supports_fields(std::slice::from_ref(&sort_field)) {
106+
return Ok(values);
107+
}
108+
109+
let converter = RowConverter::new(vec![sort_field])?;
110+
let rows = converter.convert_columns(std::slice::from_ref(&values))?;
111+
112+
// Select the first entry of each distinct value by index. The entries are
113+
// taken from the input instead of decoded from the rows, so that the type
114+
// of the input (for example a dictionary) is kept.
115+
let mut seen: HashSet<Row> = HashSet::with_capacity(values.len());
116+
let mut indices: Vec<usize> = (0..rows.num_rows())
117+
.filter(|&idx| seen.insert(rows.row(idx)))
118+
.collect();
119+
indices.sort_unstable_by(|&a, &b| rows.row(a).cmp(&rows.row(b)));
120+
121+
let indices = UInt64Array::from_iter_values(indices.into_iter().map(|i| i as u64));
122+
Ok(take(values.as_ref(), &indices, None)?)
123+
}
124+
80125
#[cfg(test)]
81126
mod tests {
82127
use super::*;
@@ -155,4 +200,25 @@ mod tests {
155200
assert_eq!(result.len(), 3);
156201
assert_eq!(result.data_type(), dict_array.data_type());
157202
}
203+
204+
#[test]
205+
fn test_sorted_distinct_inlist_values_keeps_dictionary_type() {
206+
let keys = Int8Array::from(vec![1i8, 0, 1, 1, 0]);
207+
let values = Arc::new(StringArray::from(vec!["foo", "bar"]));
208+
let dict_array = Arc::new(DictionaryArray::new(keys, values)) as ArrayRef;
209+
210+
let result = sorted_distinct_inlist_values(Arc::clone(&dict_array)).unwrap();
211+
212+
assert_eq!(result.data_type(), dict_array.data_type());
213+
assert_eq!(result.len(), 2);
214+
// "bar" sorts before "foo".
215+
assert_eq!(
216+
arrow::util::display::array_value_to_string(&result, 0).unwrap(),
217+
"bar"
218+
);
219+
assert_eq!(
220+
arrow::util::display::array_value_to_string(&result, 1).unwrap(),
221+
"foo"
222+
);
223+
}
158224
}

0 commit comments

Comments
 (0)