Refactor InListExpr to support structs by re-using existing hashing infrastructure #18449

adriangb · 2025-11-02T18:53:27Z

Background

This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in #17171.

A "target state" is tracked in #18393.
There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own:

Refactor create_hashes to accept array references #18448
(This PR): Refactor InListExpr to support structs by re-using existing hashing infrastructure #18449 (depends on Refactor create_hashes to accept array references #18448)
Refactor state management in HashJoinExec and use CASE expressions for more precise filters #18451

Changes in this PR

Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec
by adding an internal InListStorage enum with Array and Exprs variants
Re-use existing hashing and comparison utilities to support Struct arrays and other complex types
Add public function in_list_from_array(expr, list_array, negated) for creating InList from arrays

Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types).

adriangb · 2025-11-02T18:54:08Z

datafusion/proto/src/physical_plan/to_proto.rs

+                    // TODO: serialize the inner ArrayRef directly to avoid materialization into literals
+                    // by extending the protobuf definition to support both representations and adding a public
+                    // accessor method to InListExpr to get the inner ArrayRef


I'll create a followup issue once we merge this

adriangb · 2025-11-02T18:54:38Z

datafusion/sqllogictest/test_files/array.slt

 05)--------ProjectionExec: expr=[]
 06)----------CoalesceBatchesExec: target_batch_size=8192
-07)------------FilterExec: substr(md5(CAST(value@0 AS Utf8View)), 1, 32) IN ([7f4b18de3cfeb9b4ac78c381ee2ad278, a, b, c])
+07)------------FilterExec: substr(md5(CAST(value@0 AS Utf8View)), 1, 32) IN (SET) ([7f4b18de3cfeb9b4ac78c381ee2ad278, a, b, c])


This is because we now support Utf8View for building the sets 😄

adriangb · 2025-11-02T18:56:22Z

datafusion/physical-expr/src/expressions/in_list.rs

+                let random_state = RandomState::with_seed(0);
+                let mut hashes_buf = vec![0u64; array.len()];
+                let Ok(hashes_buf) = create_hashes_from_arrays(
+                    &[array.as_ref()],
+                    &random_state,
+                    &mut hashes_buf,
+                ) else {
+                    unreachable!("Failed to create hashes for InList array. This shouldn't happen because make_set should have succeeded earlier.");
+                };
+                hashes_buf.hash(state);


We could pre-compute and store a hash: u64 which would be both more performant when Hash is called and avoid this error, but it would add more complexity and some overhead when building the InListExpr

## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - (This PR): apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 ## Changes in this PR Change create_hashes and related functions to work with &dyn Array references instead of requiring ArrayRef (Arc-wrapped arrays). This avoids unnecessary Arc::clone() calls and enables calls that only have an &dyn Array to use the hashing utilities. - Add create_hashes_from_arrays(&[&dyn Array]) function - Refactor hash_dictionary, hash_list_array, hash_fixed_list_array to use references instead of cloning - Extract hash_single_array() helper for common logic --------- Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org>

adriangb · 2025-11-07T19:10:52Z

datafusion/physical-expr/src/utils/guarantee.rs

    /// supported. Returns None otherwise. See [`LiteralGuarantee::analyze`] to
    /// create these structures from an predicate (boolean expression).
-    fn new<'a>(
+    fn new(


I think it's worth discussing in this review how far we propagate the changes.

In particular, InListExpr will now have two operations modes:

Was built with an ArrayRef or was able to build an ArrayRef from a homogeneously typed Vec<Arc<dyn PhysicalExpr>> which are all literals.

Was built with a Vec<Arc<dyn PhysicalExpr>> which are not literals or homogeneously typed.

If we restrict LiteralGuarantee to only operate on the first cases, I think we could lift out a lot of computation: instead of transforming ArrayRef -> Vec<Arc<dyn PhysicalExpr>> -> Vec<ScalarValue> -> HashSet<ScalarValue> which then gets fed into bloom filters which are per-column and don't really support heterogenous ScalarValues we could re-use the already deduplicated ArraySet that InListExpr has internally or something. The ultimate thing to do, but that would require even more work and changes, would be to make PruningPredicate::contains accept an enum ArrayOrScalars { Array(ArrayRef), Scalars(Vec<ScalarValue>) } so that we can push down and iterate over the Arc'ed ArrayRef the whole way down. I think we could make this backwards compatible.

I think that change is worth it, but it requires a bit more coordination (with arrow-rs) and a bigger change.

The end result would be that:

When you create an InListExpr operates in mode (1) we are able to push down into bloom filters with no data copies at all.

When the InListExpr operates in mode (2) we'd bail on the pushdown early (e.g. list() -> Option<ArrayRef>) and avoid building the HashSet<ScalarValue>, etc. that won't be used.

Wdyt @alamb ?

Okay I've looked into this and it is entirely possible, I think we should do it.
Basically the status quo currently is that we always try to build an ArrayHashSet which is only possible if we can convert the Vec<ScalarValue> into an ArrayRef.

At that point the only reason to store the Vec<SclarValue> is to later pass it into PruningPredicate -> bloom filters and LiteralGuarantee. If we can refactor those two to also handle an ArrayRef we could probably avoid a lot of cloning and make things more efficient by using arrays. I don't even think we need to support Vec<ScalarValue> at all: the only reason to have that is if you could not build a homogeneously typed array, and if that is the case you probably can't do any sort of pushdown into a bloom filter. E.g. select variant_get(col, 'abc') in (1, 2.0, 'c') might make sense and work but I don't think we could ever push that down into a bloom filter. So InListExpr needs to operate on both but I don't think the pruning machinery does.

So anyway I think I may try to reduce this change to only be about using create_hashes and ignore any inefficiencies as a TODO for a followup issue. At the end of the day if we can make HashJoinExec faster even if that's with some inefficiencies I think that's okay and we can improve more later.

I'll record a preview of some of the changes I had made to explore this (by no means ready) just for future reference: https://github.com/pydantic/datafusion/compare/refactor-in-list...pydantic:datafusion:use-array-in-pruning?expand=1

adriangb · 2025-11-09T07:01:03Z

datafusion/physical-expr/src/expressions/in_list.rs

-pub trait Set: Send + Sync {
-    fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray>;
-    fn has_nulls(&self) -> bool;
-}


We get rid of the Set trait. The only implementer was ArraySet

adriangb · 2025-11-09T07:03:07Z

datafusion/physical-expr/src/expressions/in_list.rs

-        array => Arc::new(ArraySet::new(array, make_hash_set(array))),
-        DataType::Boolean => {
-            let array = as_boolean_array(array)?;
-            Arc::new(ArraySet::new(array, make_hash_set(array)))
-        },


We get rid of this type matching logic

adriangb · 2025-11-09T07:03:32Z

datafusion/physical-expr/src/expressions/in_list.rs

-trait IsEqual: HashValue {
-    fn is_equal(&self, other: &Self) -> bool;
-}
-
-impl<T: IsEqual + ?Sized> IsEqual for &T {
-    fn is_equal(&self, other: &Self) -> bool {
-        T::is_equal(self, other)
-    }
-}


We get rid of these custom equality / hash traits

alamb · 2025-11-09T16:26:11Z

🤖 ./gh_compare_branch_bench.sh Benchmark Script Running
Linux aal-dev 6.14.0-1018-gcp #19~24.04.1-Ubuntu SMP Wed Sep 24 23:23:09 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
Comparing refactor-in-list (f412ead) to 1d8bc9b diff
BENCH_NAME=in_list
BENCH_COMMAND=cargo bench --bench in_list
BENCH_FILTER=
BENCH_BRANCH_NAME=refactor-in-list
Results will be posted here when complete

alamb

Thanks @adriangb

I looked through the code and the basic idea makes a lot of sense to me 👍

I kicked off some benchmarks to see what impact, if any, this change has on performance. Assuming it is the same or better, I think it would be good to merge

I do suggest adding some slt level logic for struct IN lists if we don't already have some, but I don't think it is necessary

alamb · 2025-11-09T16:34:15Z

datafusion/physical-expr/src/expressions/in_list.rs

-                        false => Some(negated),
-                    }
-                })
+        let mut hashes_buf = vec![0u64; v.len()];


As a follow on PR we could potentially look into reusing this hashes_buf -- aka rather than reallocating each invocations of contains instead make a field (probably needs to be a Mutex or something) that is a Vec

alamb · 2025-11-09T16:36:56Z

datafusion/physical-expr/src/expressions/in_list.rs

-                })
+        let mut hashes_buf = vec![0u64; v.len()];
+        create_hashes([v], &self.state, &mut hashes_buf)?;
+        let cmp = make_comparator(v, in_array, SortOptions::default())?;


the comparator is some dynamic function -- the overhead of using the dynamic dispatch in the critical path may be substantial).

If it turns out to be too slow, we can potentially create specializations for comparisons (aka make a speicalized hash set for the different physical array types, and fall back to the dynamic comparator)

alamb · 2025-11-09T16:38:12Z

datafusion/physical-expr/src/expressions/in_list.rs

+///
+/// The `list` field will be empty when using this constructor, as the array is stored
+/// directly in the static filter.
+pub fn in_list_from_array(


I wonder if it would be more discoverable if this was a method on InList rather than a free function

Something like

impl InLIst fn new_from_array( expr: Arc<dyn PhysicalExpr>, array: ArrayRef, negated: bool, ) -> Result<Self> { ... }

Yeah I agree, I was just following the existing patterns

alamb · 2025-11-09T16:38:37Z

datafusion/physical-expr/src/expressions/in_list.rs

    }
+
+    #[test]
+    fn in_list_struct() -> Result<()> {


Can we also please add some .slt level tests for IN on a set?

alamb · 2025-11-09T16:45:35Z

🤖: Benchmark completed

Details

group                                       main                                   refactor-in-list
-----                                       ----                                   ----------------
in_list_f32 (1024, 0) IN (1, 0)             1.00      4.3±0.01µs        ? ?/sec    1.14      4.9±0.01µs        ? ?/sec
in_list_f32 (1024, 0) IN (10, 0)            1.00      4.3±0.01µs        ? ?/sec    1.14      4.9±0.01µs        ? ?/sec
in_list_f32 (1024, 0) IN (100, 0)           1.00      4.2±0.03µs        ? ?/sec    1.14      4.9±0.01µs        ? ?/sec
in_list_f32 (1024, 0) IN (3, 0)             1.00      4.2±0.01µs        ? ?/sec    1.15      4.9±0.01µs        ? ?/sec
in_list_f32 (1024, 0.2) IN (1, 0)           1.00      5.5±0.06µs        ? ?/sec    1.36      7.5±0.03µs        ? ?/sec
in_list_f32 (1024, 0.2) IN (10, 0)          1.00      5.5±0.06µs        ? ?/sec    1.40      7.7±0.07µs        ? ?/sec
in_list_f32 (1024, 0.2) IN (100, 0)         1.00      5.6±0.03µs        ? ?/sec    1.23      6.9±0.06µs        ? ?/sec
in_list_f32 (1024, 0.2) IN (3, 0)           1.00      5.5±0.06µs        ? ?/sec    1.38      7.6±0.03µs        ? ?/sec
in_list_i32 (1024, 0) IN (1, 0)             1.00      4.2±0.01µs        ? ?/sec    1.16      4.9±0.01µs        ? ?/sec
in_list_i32 (1024, 0) IN (10, 0)            1.00      4.2±0.01µs        ? ?/sec    1.16      4.9±0.01µs        ? ?/sec
in_list_i32 (1024, 0) IN (100, 0)           1.00      4.2±0.01µs        ? ?/sec    1.16      4.9±0.01µs        ? ?/sec
in_list_i32 (1024, 0) IN (3, 0)             1.00      4.2±0.01µs        ? ?/sec    1.16      4.9±0.01µs        ? ?/sec
in_list_i32 (1024, 0.2) IN (1, 0)           1.00      5.7±0.02µs        ? ?/sec    1.31      7.5±0.04µs        ? ?/sec
in_list_i32 (1024, 0.2) IN (10, 0)          1.00      5.6±0.01µs        ? ?/sec    1.29      7.2±0.04µs        ? ?/sec
in_list_i32 (1024, 0.2) IN (100, 0)         1.00      5.5±0.03µs        ? ?/sec    1.22      6.7±0.04µs        ? ?/sec
in_list_i32 (1024, 0.2) IN (3, 0)           1.00      5.7±0.04µs        ? ?/sec    1.31      7.5±0.03µs        ? ?/sec
in_list_utf8(10) (1024, 0) IN (1, 0)        1.09      5.5±0.02µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(10) (1024, 0) IN (10, 0)       1.09      5.5±0.01µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(10) (1024, 0) IN (100, 0)      1.05      5.5±0.05µs        ? ?/sec    1.00      5.3±0.03µs        ? ?/sec
in_list_utf8(10) (1024, 0) IN (3, 0)        1.13      5.7±0.06µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(10) (1024, 0.2) IN (1, 0)      1.00      7.6±0.04µs        ? ?/sec    1.05      8.0±0.07µs        ? ?/sec
in_list_utf8(10) (1024, 0.2) IN (10, 0)     1.00      7.8±0.04µs        ? ?/sec    1.01      7.8±0.03µs        ? ?/sec
in_list_utf8(10) (1024, 0.2) IN (100, 0)    1.03      8.0±0.09µs        ? ?/sec    1.00      7.8±0.07µs        ? ?/sec
in_list_utf8(10) (1024, 0.2) IN (3, 0)      1.00      7.7±0.04µs        ? ?/sec    1.06      8.1±0.06µs        ? ?/sec
in_list_utf8(20) (1024, 0) IN (1, 0)        1.10      5.6±0.19µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(20) (1024, 0) IN (10, 0)       1.09      5.5±0.01µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(20) (1024, 0) IN (100, 0)      1.09      5.5±0.01µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(20) (1024, 0) IN (3, 0)        1.04      5.5±0.01µs        ? ?/sec    1.00      5.3±0.01µs        ? ?/sec
in_list_utf8(20) (1024, 0.2) IN (1, 0)      1.00      7.9±0.03µs        ? ?/sec    1.01      8.0±0.03µs        ? ?/sec
in_list_utf8(20) (1024, 0.2) IN (10, 0)     1.00      7.9±0.10µs        ? ?/sec    1.00      7.9±0.06µs        ? ?/sec
in_list_utf8(20) (1024, 0.2) IN (100, 0)    1.00      7.8±0.03µs        ? ?/sec    1.00      7.8±0.05µs        ? ?/sec
in_list_utf8(20) (1024, 0.2) IN (3, 0)      1.02      8.2±0.08µs        ? ?/sec    1.00      8.0±0.05µs        ? ?/sec
in_list_utf8(5) (1024, 0) IN (1, 0)         1.12      5.7±0.05µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(5) (1024, 0) IN (10, 0)        1.09      5.5±0.01µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(5) (1024, 0) IN (100, 0)       1.09      5.5±0.01µs        ? ?/sec    1.00      5.0±0.02µs        ? ?/sec
in_list_utf8(5) (1024, 0) IN (3, 0)         1.09      5.5±0.02µs        ? ?/sec    1.00      5.1±0.01µs        ? ?/sec
in_list_utf8(5) (1024, 0.2) IN (1, 0)       1.00      7.6±0.02µs        ? ?/sec    1.03      7.8±0.08µs        ? ?/sec
in_list_utf8(5) (1024, 0.2) IN (10, 0)      1.00      7.8±0.05µs        ? ?/sec    1.00      7.8±0.03µs        ? ?/sec
in_list_utf8(5) (1024, 0.2) IN (100, 0)     1.00      7.7±0.03µs        ? ?/sec    1.00      7.7±0.06µs        ? ?/sec
in_list_utf8(5) (1024, 0.2) IN (3, 0)       1.04      8.0±0.04µs        ? ?/sec    1.00      7.7±0.05µs        ? ?/sec

adriangb · 2025-11-09T17:51:44Z

It looks like there are indeed some regressions. I propose we do two things:

Add a create_hashes_unbuffered(…) -> &[u64] that uses a thread local to re-use the buffer. I think this will be helpful in other contexts as well.
Create a make_typed_comparator that returns an enum that is typed for non-recursive types and delegates to a fallback dynamically typed variant for recursive types. I’ll implement it here for now but make a note that it would be good to upstream into arrow. When it is up streamed into arrow we can re-implement the current version in terms of their new version and deprecate the current function.

I think that will get us the broader type support and code re-use while avoiding any slowdown. Once we do the upstreaming into arrow it won’t even be any more code than it is now (a bit more code in arrow but not even that much). And we should be able to do it all in one PR here

* Consolidate StaticFilter and ArrayHashSet * Fix docs

adriangb · 2025-11-18T09:31:54Z

I'm surprised that doing dynamic dispatch once per batch we evaluate as opposed to twice per batch we evaluate makes that much of a difference. What would make sense that makes a difference to me is doing it once per element vs. once per batch. But I guess that's what benchmarks say!

That does leave me with a question... could we squeeze out even more performance if we specialize for ~ all scalar types? It wouldn't be that hard to write a macro and have AI do the copy pasta of implementing it for all of the types... I'll open a follow up ticket.

adriangb · 2025-11-18T09:32:14Z

Also thank you for your help getting this across the line @alamb! I'm excited to continue the work.

alamb · 2025-11-19T16:01:56Z

That does leave me with a question... could we squeeze out even more performance if we specialize for ~ all scalar types? It wouldn't be that hard to write a macro and have AI do the copy pasta of implementing it for all of the types... I'll open a follow up ticket.

Yes this is what I think we should do

alamb · 2025-11-19T16:02:37Z

datafusion/physical-expr/src/expressions/in_list.rs

+}

-    ArrayHashSet { state, map }
+struct Int32StaticFilter {


Oh yeah, we should totally do the same thing here for the other types. I'll file a ticket to track that

alamb · 2025-11-19T18:33:05Z

Filed Restore IN_LIST performance -- Implement specialized StaticFilters for different data types #18824

…for more precise filters (#18451) ## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in #17171. A "target state" is tracked in #18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - #18448 - #18449 (depends on #18448) - (This PR): #18451 ## Changes in this PR This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com>

…nfrastructure (apache#18449) ## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - (This PR): apache#18449 (depends on apache#18448) - apache#18451 ## Changes in this PR - Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec<PhysicalExpr> by adding an internal InListStorage enum with Array and Exprs variants - Re-use existing hashing and comparison utilities to support Struct arrays and other complex types - Add public function `in_list_from_array(expr, list_array, negated)` for creating InList from arrays Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types). --------- Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org>

…for more precise filters (apache#18451) ## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - (This PR): apache#18451 ## Changes in this PR This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com>

… on the size of the build side (#18393) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in #17171. A "target state" is tracked in #18393 (*this PR*). There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - #18448 - #18449 (depends on #18448) - #18451 As those are merged I will rebase this PR to keep track of the "remaining work", and we can use this PR to explore big picture ideas or benchmarks of the final state.

This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - (This PR): apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 Change create_hashes and related functions to work with &dyn Array references instead of requiring ArrayRef (Arc-wrapped arrays). This avoids unnecessary Arc::clone() calls and enables calls that only have an &dyn Array to use the hashing utilities. - Add create_hashes_from_arrays(&[&dyn Array]) function - Refactor hash_dictionary, hash_list_array, hash_fixed_list_array to use references instead of cloning - Extract hash_single_array() helper for common logic --------- Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit a899ca0)

…nfrastructure (apache#18449) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - (This PR): apache#18449 (depends on apache#18448) - apache#18451 - Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec<PhysicalExpr> by adding an internal InListStorage enum with Array and Exprs variants - Re-use existing hashing and comparison utilities to support Struct arrays and other complex types - Add public function `in_list_from_array(expr, list_array, negated)` for creating InList from arrays Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types). --------- Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit 486c5d8)

…for more precise filters (apache#18451) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - (This PR): apache#18451 This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com> (cherry picked from commit 5b0aa37)

… on the size of the build side (apache#18393) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393 (*this PR*). There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 As those are merged I will rebase this PR to keep track of the "remaining work", and we can use this PR to explore big picture ideas or benchmarks of the final state. (cherry picked from commit c0e8bb5)

This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - (This PR): apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 Change create_hashes and related functions to work with &dyn Array references instead of requiring ArrayRef (Arc-wrapped arrays). This avoids unnecessary Arc::clone() calls and enables calls that only have an &dyn Array to use the hashing utilities. - Add create_hashes_from_arrays(&[&dyn Array]) function - Refactor hash_dictionary, hash_list_array, hash_fixed_list_array to use references instead of cloning - Extract hash_single_array() helper for common logic --------- Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit a899ca0) (cherry picked from commit e53debb)

…nfrastructure (apache#18449) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - (This PR): apache#18449 (depends on apache#18448) - apache#18451 - Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec<PhysicalExpr> by adding an internal InListStorage enum with Array and Exprs variants - Re-use existing hashing and comparison utilities to support Struct arrays and other complex types - Add public function `in_list_from_array(expr, list_array, negated)` for creating InList from arrays Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types). --------- Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit 486c5d8) (cherry picked from commit 181e058)

…for more precise filters (apache#18451) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - (This PR): apache#18451 This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com> (cherry picked from commit 5b0aa37) (cherry picked from commit e9d1985)

… on the size of the build side (apache#18393) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393 (*this PR*). There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 As those are merged I will rebase this PR to keep track of the "remaining work", and we can use this PR to explore big picture ideas or benchmarks of the final state. (cherry picked from commit c0e8bb5) (cherry picked from commit 115313c)

…nfrastructure (apache#18449) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - (This PR): apache#18449 (depends on apache#18448) - apache#18451 - Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec<PhysicalExpr> by adding an internal InListStorage enum with Array and Exprs variants - Re-use existing hashing and comparison utilities to support Struct arrays and other complex types - Add public function `in_list_from_array(expr, list_array, negated)` for creating InList from arrays Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types). --------- Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit 486c5d8)

…for more precise filters (apache#18451) ## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - (This PR): apache#18451 ## Changes in this PR This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com> (cherry picked from commit 5b0aa37)

… on the size of the build side (apache#18393) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393 (*this PR*). There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 As those are merged I will rebase this PR to keep track of the "remaining work", and we can use this PR to explore big picture ideas or benchmarks of the final state. (cherry picked from commit c0e8bb5)

* Refactor InListExpr to support structs by re-using existing hashing infrastructure (apache#18449) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - (This PR): apache#18449 (depends on apache#18448) - apache#18451 - Enhance InListExpr to efficiently store homogeneous lists as arrays and avoid a conversion to Vec<PhysicalExpr> by adding an internal InListStorage enum with Array and Exprs variants - Re-use existing hashing and comparison utilities to support Struct arrays and other complex types - Add public function `in_list_from_array(expr, list_array, negated)` for creating InList from arrays Although the diff looks large most of it is actually tests and docs. I think the actual code change is a negative LOC change, or at least negative complexity (eliminates a trait, a macro, matching on data types). --------- Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> (cherry picked from commit 486c5d8) * feat: Add evaluate_to_arrays function (apache#18446) ## Which issue does this PR close?  - Closes apache#18330 . ## Rationale for this change  Reduce code duplication. ## What changes are included in this PR?  A util function replacing many calls which are using the same code. ## Are these changes tested?  No logic should change whatsoever, so each area which now uses this code should have it's own tests and benchmarks unmodified. ## Are there any user-facing changes?   Yes, there is now a new pub function. No other changes to API. --------- Co-authored-by: Martin Grigorov <martin-g@users.noreply.github.com> (cherry picked from commit 76b4156) * Refactor state management in `HashJoinExec` and use CASE expressions for more precise filters (apache#18451) ## Background This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393. There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - (This PR): apache#18451 ## Changes in this PR This PR refactors state management in HashJoinExec to make filter pushdown more efficient and prepare for pushing down membership tests. - Refactor internal data structures to clean up state management and make usage more idiomatic (use `Option` instead of comparing integers, etc.) - Uses CASE expressions to evaluate pushed-down filters selectively by partition Example: `CASE hash_repartition % N WHEN partition_id THEN condition ELSE false END` --------- Co-authored-by: Lía Adriana <lia.castaneda@datadoghq.com> (cherry picked from commit 5b0aa37) * Push down InList or hash table references from HashJoinExec depending on the size of the build side (apache#18393) This PR is part of an EPIC to push down hash table references from HashJoinExec into scans. The EPIC is tracked in apache#17171. A "target state" is tracked in apache#18393 (*this PR*). There is a series of PRs to get us to this target state in smaller more reviewable changes that are still valuable on their own: - apache#18448 - apache#18449 (depends on apache#18448) - apache#18451 As those are merged I will rebase this PR to keep track of the "remaining work", and we can use this PR to explore big picture ideas or benchmarks of the final state. (cherry picked from commit c0e8bb5) * fmt * replace HashTableLookupExpr with lit(true) in proto serialization (apache#19300) *errors* when serializing now, and would break any users using joins + protobuf. --------- Co-authored-by: Adrian Garcia Badaracco <1755071+adriangb@users.noreply.github.com> Co-authored-by: David Hewitt <mail@davidhewitt.dev> Co-authored-by: Andrew Lamb <andrew@nerdnetworks.org> Co-authored-by: Emily Matheys <55631053+EmilyMatt@users.noreply.github.com> Co-authored-by: Martin Grigorov <martin-g@users.noreply.github.com>

github-actions bot added physical-expr Changes to the physical-expr crates sqllogictest SQL Logic Tests (.slt) common Related to common crate proto Related to proto crate physical-plan Changes to the physical-plan crate labels Nov 2, 2025

adriangb commented Nov 2, 2025

View reviewed changes

adriangb force-pushed the refactor-in-list branch from 4d4b797 to 9a0f6be Compare November 2, 2025 20:48

adriangb mentioned this pull request Nov 2, 2025

Push down InList or hash table references from HashJoinExec depending on the size of the build side #18393

Merged

adriangb force-pushed the refactor-in-list branch from 9a0f6be to f1f3b66 Compare November 2, 2025 21:13

This was referenced Nov 3, 2025

Push down entire hash table from HashJoinExec into scans #17171

Closed

Refactor create_hashes to accept array references #18448

Merged

Refactor state management in HashJoinExec and use CASE expressions for more precise filters #18451

Merged

alamb mentioned this pull request Nov 4, 2025

Andrew Lamb Weekly-ish Open Source plan - 2025-11-03 #18486

Closed

53 tasks

adriangb force-pushed the refactor-in-list branch from f1f3b66 to d1b9d05 Compare November 7, 2025 18:25

github-actions bot removed common Related to common crate physical-plan Changes to the physical-plan crate labels Nov 7, 2025

adriangb commented Nov 7, 2025

View reviewed changes

github-actions bot removed the proto Related to proto crate label Nov 9, 2025

adriangb changed the title ~~Refactor InListExpr to store arrays and support structs~~ Refactor InListExpr to support structs by re-using existing hashing infrastructure Nov 9, 2025

adriangb commented Nov 9, 2025

View reviewed changes

adriangb force-pushed the refactor-in-list branch from ab74641 to f412ead Compare November 9, 2025 15:15

alamb reviewed Nov 9, 2025

View reviewed changes

github-actions bot added the common Related to common crate label Nov 10, 2025

alamb and others added 2 commits November 18, 2025 17:03

Consolidate StaticFilter and ArrayHashSet (#44)

621cfe5

* Consolidate StaticFilter and ArrayHashSet * Fix docs

fix rebase

8a2ee06

adriangb force-pushed the refactor-in-list branch from 2f5e435 to 8a2ee06 Compare November 18, 2025 09:19

Add specialized sets for primitive types

06a4763

adriangb added this pull request to the merge queue Nov 18, 2025

Merged via the queue into apache:main with commit 486c5d8 Nov 18, 2025
32 checks passed

adriangb deleted the refactor-in-list branch November 18, 2025 23:37

alamb reviewed Nov 19, 2025

View reviewed changes

alamb mentioned this pull request Nov 19, 2025

Restore IN_LIST performance -- Implement specialized StaticFilters for different data types #18824

Closed

Refactor InListExpr to support structs by re-using existing hashing infrastructure #18449

Refactor InListExpr to support structs by re-using existing hashing infrastructure #18449

Uh oh!

Conversation

adriangb commented Nov 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Background

Changes in this PR

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alamb commented Nov 9, 2025

Uh oh!

alamb left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alamb commented Nov 9, 2025

Uh oh!

adriangb commented Nov 9, 2025

Uh oh!

adriangb commented Nov 18, 2025

Uh oh!

adriangb commented Nov 18, 2025

Uh oh!

Uh oh!

alamb commented Nov 19, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alamb commented Nov 19, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

adriangb commented Nov 2, 2025 •

edited

Loading