@@ -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