Skip to content

Commit 7a8272f

Browse files
adriangbclaude
andcommitted
refactor: dedup cross-partition InList, reuse per-partition cap
The cross-partition merged-InList gate now reuses the existing `optimizer.hash_join_inlist_pushdown_max_distinct_values` knob: one configuration option caps both the per-partition InList pushdown and the cross-partition merged set. The combine path explicitly deduplicates by `ScalarValue` (via a HashSet first-seen walk + a single `arrow::compute::take`) and then re-gates on the distinct count rather than the previous total-array-length heuristic. With the cap defaulting to 20, the worst-case dedup input is N×20 entries, which is microseconds at the partition counts we see in practice. The previous hardcoded 20-entry length cap and `MERGED_INLIST_MAX_TOTAL_LEN` constant are gone — the threshold is now configurable. Default lowered from 150 → 20 to align with parquet stats / bloom-filter pruning practicality (a small `IN (SET)` that scans can use to drop row groups is the entire reason for keeping this path). Users that want the wider per-partition InList behavior can raise the value. Within-partition build still ships duplicates: the build code in `exec.rs` doesn't dedupe before populating `PushdownStrategy::inlist`, relying on the join hash map's `num_of_distinct_key()` for the per-partition gate and the static filter inside `InListExpr` to dedupe at filter-evaluation time. Adding explicit per-partition dedup is a follow-up — not required for correctness because the cross-partition dedup catches everything. Refs: #19858 Co-Authored-By: Claude Opus 4.7 (1M context) <[email protected]>
1 parent e58daab commit 7a8272f

4 files changed

Lines changed: 87 additions & 51 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1309,11 +1309,15 @@ config_namespace! {
13091309
/// very large IN lists that might not provide much benefit over hash table lookups.
13101310
///
13111311
/// This uses the deduplicated row count once the build side has been evaluated.
1312+
/// In `Partitioned` hash-join mode the same threshold also gates the
1313+
/// cross-partition merged InList: per-partition InList arrays are
1314+
/// concatenated and deduplicated, and the merged `IN (SET)` only fires
1315+
/// when the union has at most this many distinct values.
13121316
///
1313-
/// The default is 150 values per partition.
1314-
/// This is inspired by Trino's `max-filter-keys-per-column` setting.
1315-
/// See: <https://trino.io/docs/current/admin/dynamic-filtering.html#dynamic-filter-collection-thresholds>
1316-
pub hash_join_inlist_pushdown_max_distinct_values: usize, default = 150
1317+
/// The default is 20 distinct values, tuned so the resulting `IN (SET)`
1318+
/// stays small enough to participate in parquet stats / bloom-filter
1319+
/// pruning at the scan side.
1320+
pub hash_join_inlist_pushdown_max_distinct_values: usize, default = 20
13171321

13181322
/// The default filter selectivity used by Filter Statistics
13191323
/// when an exact selectivity cannot be determined. Valid values are

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

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1327,13 +1327,19 @@ impl ExecutionPlan for HashJoinExec {
13271327
.iter()
13281328
.map(|(_, right_expr)| Arc::clone(right_expr))
13291329
.collect::<Vec<_>>();
1330+
let inlist_max_distinct_values = context
1331+
.session_config()
1332+
.options()
1333+
.optimizer
1334+
.hash_join_inlist_pushdown_max_distinct_values;
13301335
Some(Arc::clone(df.build_accumulator.get_or_init(|| {
13311336
Arc::new(SharedBuildAccumulator::new_from_partition_mode(
13321337
self.mode,
13331338
self.left.as_ref(),
13341339
self.right.as_ref(),
13351340
filter,
13361341
on_right,
1342+
inlist_max_distinct_values,
13371343
))
13381344
})))
13391345
})

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

Lines changed: 72 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -302,6 +302,15 @@ pub(crate) struct SharedBuildAccumulator {
302302
on_right: Vec<PhysicalExprRef>,
303303
/// Schema of the probe (right) side for evaluating filter expressions
304304
probe_schema: Arc<Schema>,
305+
/// Cap on the cross-partition merged-InList distinct count. Reuses
306+
/// `optimizer.hash_join_inlist_pushdown_max_distinct_values` (the same
307+
/// option that gates per-partition InList pushdown). When the union of
308+
/// every reported partition's deduplicated InList values stays at or
309+
/// below this many distinct entries we collapse them into a single
310+
/// `IN (SET)` predicate that can participate in parquet stats /
311+
/// bloom-filter pruning at the scan; otherwise we use
312+
/// `multi_hash_lookup` over every partition's hash table instead.
313+
inlist_max_distinct_values: usize,
305314
}
306315

307316
/// Build-side data needed to construct a dynamic filter for one partition.
@@ -438,6 +447,7 @@ impl SharedBuildAccumulator {
438447
right_child: &dyn ExecutionPlan,
439448
dynamic_filter: Arc<DynamicFilterPhysicalExpr>,
440449
on_right: Vec<PhysicalExprRef>,
450+
inlist_max_distinct_values: usize,
441451
) -> Self {
442452
// Troubleshooting: If partition counts are incorrect, verify this logic matches
443453
// the actual execution pattern in collect_build_side()
@@ -483,6 +493,7 @@ impl SharedBuildAccumulator {
483493
dynamic_filter,
484494
on_right,
485495
probe_schema: right_child.schema(),
496+
inlist_max_distinct_values,
486497
}
487498
}
488499

@@ -733,9 +744,11 @@ impl SharedBuildAccumulator {
733744
/// Cheap short-circuit and the only piece visible to scan-level
734745
/// `pruning_predicate` extraction.
735746
/// * `merged_in_list` — concatenated build keys when every reported
736-
/// partition produced an `InList` array and the cross-partition union
737-
/// is small enough (≤ `MERGED_INLIST_MAX_TOTAL_LEN`). Worth carrying
738-
/// because a small `IN (SET)` participates in parquet stats /
747+
/// partition produced an `InList` array and the cross-partition
748+
/// *deduplicated* set has at most `inlist_max_distinct_values` distinct
749+
/// entries (the same option that gates the per-partition InList path,
750+
/// `optimizer.hash_join_inlist_pushdown_max_distinct_values`). Worth
751+
/// carrying because a small `IN (SET)` participates in parquet stats /
739752
/// bloom-filter pruning, which `multi_hash_lookup` cannot.
740753
/// * `multi_hash_lookup` — runtime hash-table probe across every
741754
/// partition's `Map`, hashing the join keys once.
@@ -763,77 +776,89 @@ impl SharedBuildAccumulator {
763776
.as_ref()
764777
.and_then(|b| create_bounds_predicate(&self.on_right, b));
765778

766-
// Threshold on the cross-partition merged InList. Two reasons for
767-
// keeping it small:
768-
// 1. Below this many values the merged `IN (SET)` can participate
769-
// in parquet stats / bloom-filter pruning at the scan; a
770-
// `multi_hash_lookup` cannot.
771-
// 2. Past this size the larger static_filter hash set blows out
772-
// of L1 and runtime regresses. A TPC-H SF=1 cap sweep from 20
773-
// to 2000 picked 20–50 as the sweet spot.
774-
const MERGED_INLIST_MAX_TOTAL_LEN: usize = 20;
775-
776779
// Try to build a merged InList. Only fires when *every* reported
777780
// partition contributed an InList array AND the cross-partition
778-
// union is small. The merged InList is already the union of every
781+
// deduplicated union has at most `inlist_max_distinct_values`
782+
// entries. The merged InList already covers the union of every
779783
// partition's build-side keys, so when present it fully replaces
780784
// `multi_hash_lookup` — no need to AND a redundant probe on top.
781-
let membership_expr = if let Some(merged) =
782-
self.try_build_merged_inlist(real_partitions, MERGED_INLIST_MAX_TOTAL_LEN)?
783-
{
784-
Some(merged)
785-
} else {
786-
let maps: Vec<Arc<Map>> = real_partitions
787-
.iter()
788-
.filter_map(|p| p.pushdown.map.clone())
789-
.collect();
790-
if maps.is_empty() {
791-
// Defensive: every reported (non-empty) partition is
792-
// supposed to carry a Map. Falling through to None means
793-
// we degrade to bounds-only filtering.
794-
None
785+
let membership_expr =
786+
if let Some(merged) = self.try_build_merged_inlist(real_partitions)? {
787+
Some(merged)
795788
} else {
796-
Some(Arc::new(MultiMapLookupExpr::new(
797-
self.on_right.clone(),
798-
HASH_JOIN_SEED.clone(),
799-
maps,
800-
"multi_hash_lookup".to_string(),
801-
)) as Arc<dyn PhysicalExpr>)
802-
}
803-
};
789+
let maps: Vec<Arc<Map>> = real_partitions
790+
.iter()
791+
.filter_map(|p| p.pushdown.map.clone())
792+
.collect();
793+
if maps.is_empty() {
794+
// Defensive: every reported (non-empty) partition is
795+
// supposed to carry a Map. Falling through to None means
796+
// we degrade to bounds-only filtering.
797+
None
798+
} else {
799+
Some(Arc::new(MultiMapLookupExpr::new(
800+
self.on_right.clone(),
801+
HASH_JOIN_SEED.clone(),
802+
maps,
803+
"multi_hash_lookup".to_string(),
804+
)) as Arc<dyn PhysicalExpr>)
805+
}
806+
};
804807

805808
Ok(
806809
combine_membership_and_bounds(membership_expr, global_bounds_expr)
807810
.unwrap_or_else(|| lit(true)),
808811
)
809812
}
810813

811-
/// If every reported partition contributed an InList array and their
812-
/// concatenated length stays within `cap`, return the merged
813-
/// `(struct(...))? IN (SET) ([…])` expression — otherwise `None`.
814+
/// If every reported partition contributed an InList array, concatenate
815+
/// them, deduplicate by scalar value, and gate on the
816+
/// `inlist_max_distinct_values` cap. Returns the merged
817+
/// `(struct(...))? IN (SET) ([…])` predicate built over the *deduplicated*
818+
/// keys when the cap is satisfied; `None` otherwise.
819+
///
820+
/// Per-partition arrays carry duplicates (the build side never dedups
821+
/// before shipping), so each partition's `arr.len()` is an upper bound on
822+
/// its distinct count. We start with a cheap pre-check (sum of lengths ≤
823+
/// some fast-reject limit) before the dedup walk to keep the cost
824+
/// proportional to actual partition sizes.
814825
fn try_build_merged_inlist(
815826
&self,
816827
real_partitions: &[&PartitionData],
817-
cap: usize,
818828
) -> Result<Option<Arc<dyn PhysicalExpr>>> {
819-
let mut total = 0usize;
829+
let cap = self.inlist_max_distinct_values;
820830
let mut arrays: Vec<ArrayRef> = Vec::with_capacity(real_partitions.len());
821831
for p in real_partitions {
822832
let Some(arr) = &p.pushdown.inlist else {
823833
return Ok(None);
824834
};
825-
total += arr.len();
826-
if total > cap {
827-
return Ok(None);
828-
}
829835
arrays.push(Arc::clone(arr));
830836
}
831837
let Some(merged) = merge_inlist_arrays(&arrays) else {
832838
return Ok(None);
833839
};
840+
// Walk the merged array once, recording the first index of each
841+
// distinct ScalarValue. If we cross the cap we abort early without
842+
// materialising a longer index list. `arrow::compute::take` then
843+
// produces the deduplicated array (in first-seen order, matching the
844+
// shape `InListExpr::try_new_from_array` expects).
845+
let mut seen = std::collections::HashSet::with_capacity(cap.saturating_add(1));
846+
let mut indices: Vec<u32> = Vec::with_capacity(cap.min(merged.len()));
847+
for i in 0..merged.len() {
848+
let scalar = ScalarValue::try_from_array(merged.as_ref(), i)?;
849+
if seen.insert(scalar) {
850+
if indices.len() >= cap {
851+
// One more distinct value would exceed the cap.
852+
return Ok(None);
853+
}
854+
indices.push(i as u32);
855+
}
856+
}
857+
let idx_array = arrow::array::UInt32Array::from(indices);
858+
let deduped = arrow::compute::take(merged.as_ref(), &idx_array, None)?;
834859
Ok(Some(create_inlist_predicate(
835860
&self.on_right,
836-
merged,
861+
deduped,
837862
self.probe_schema.as_ref(),
838863
)?))
839864
}
@@ -868,6 +893,7 @@ mod tests {
868893
dynamic_filter,
869894
on_right: vec![],
870895
probe_schema,
896+
inlist_max_distinct_values: 20,
871897
}
872898
}
873899

0 commit comments

Comments
 (0)