subject:"Re\: \[PR\] perfect hash join \[datafusion\]"

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3728238191

   Thank you @UBarney !


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



Dandandan merged PR #19411:
URL: https://github.com/apache/datafusion/pull/19411


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3728200782

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark tpch_sf1.json
   
   ┏━━┳━━━┳┳━━━┓
   ┃ Query┃  HEAD ┃ perfect_hj ┃Change ┃
   ┡━━╇━━━╇╇━━━┩
   │ QQuery 1 │ 197.41 ms │  193.73 ms │ no change │
   │ QQuery 2 │  92.23 ms │   78.21 ms │ +1.18x faster │
   │ QQuery 3 │ 118.66 ms │  119.31 ms │ no change │
   │ QQuery 4 │  77.39 ms │   75.23 ms │ no change │
   │ QQuery 5 │ 172.35 ms │  171.62 ms │ no change │
   │ QQuery 6 │  63.31 ms │   63.36 ms │ no change │
   │ QQuery 7 │ 211.99 ms │  201.61 ms │ no change │
   │ QQuery 8 │ 162.42 ms │  162.11 ms │ no change │
   │ QQuery 9 │ 224.05 ms │  217.71 ms │ no change │
   │ QQuery 10│ 194.29 ms │  182.13 ms │ +1.07x faster │
   │ QQuery 11│  73.85 ms │   53.93 ms │ +1.37x faster │
   │ QQuery 12│ 116.60 ms │  115.72 ms │ no change │
   │ QQuery 13│ 219.95 ms │  210.38 ms │ no change │
   │ QQuery 14│  92.07 ms │   86.02 ms │ +1.07x faster │
   │ QQuery 15│ 118.29 ms │  119.84 ms │ no change │
   │ QQuery 16│  55.78 ms │   57.05 ms │ no change │
   │ QQuery 17│ 272.93 ms │  271.63 ms │ no change │
   │ QQuery 18│ 324.23 ms │  317.09 ms │ no change │
   │ QQuery 19│ 131.86 ms │  128.52 ms │ no change │
   │ QQuery 20│ 125.68 ms │  122.17 ms │ no change │
   │ QQuery 21│ 257.67 ms │  248.54 ms │ no change │
   │ QQuery 22│  43.63 ms │   36.74 ms │ +1.19x faster │
   └──┴───┴┴───┘
   ┏━━━┳━━━┓
   ┃ Benchmark Summary ┃   ┃
   ┡━━━╇━━━┩
   │ Total Time (HEAD) │ 3346.65ms │
   │ Total Time (perfect_hj)   │ 3232.65ms │
   │ Average Time (HEAD)   │  152.12ms │
   │ Average Time (perfect_hj) │  146.94ms │
   │ Queries Faster│ 5 │
   │ Queries Slower│ 0 │
   │ Queries with No Change│17 │
   │ Queries with Failure  │ 0 │
   └───┴───┘
   ```
   
   
   
   
   
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3728198176

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (c772070b6690093fc094644b618e52bd414c70a9) to 
1037f0aa205e0d04ade7aa9973b4b4c485b696ab 
[diff](https://github.com/apache/datafusion/compare/1037f0aa205e0d04ade7aa9973b4b4c485b696ab..c772070b6690093fc094644b618e52bd414c70a9)
 using:  tpch
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3728197862

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark clickbench_extended.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │  2454.70 ms │  2388.05 ms │ no change │
   │ QQuery 1 │   972.85 ms │   921.28 ms │ +1.06x faster │
   │ QQuery 2 │  1927.43 ms │  1840.69 ms │ no change │
   │ QQuery 3 │  1207.26 ms │  1175.84 ms │ no change │
   │ QQuery 4 │  2293.93 ms │  2285.89 ms │ no change │
   │ QQuery 5 │ 28351.12 ms │ 28179.93 ms │ no change │
   │ QQuery 6 │  3856.37 ms │  3907.41 ms │ no change │
   │ QQuery 7 │  3715.67 ms │  3538.47 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳┓
   ┃ Benchmark Summary ┃┃
   ┡━━━╇┩
   │ Total Time (HEAD) │ 44779.32ms │
   │ Total Time (perfect_hj)   │ 44237.56ms │
   │ Average Time (HEAD)   │  5597.41ms │
   │ Average Time (perfect_hj) │  5529.70ms │
   │ Queries Faster│  1 │
   │ Queries Slower│  0 │
   │ Queries with No Change│  7 │
   │ Queries with Failure  │  0 │
   └───┴┘
   
   Benchmark clickbench_partitioned.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │ 1.43 ms │ 1.42 ms │ no change │
   │ QQuery 1 │49.63 ms │47.90 ms │ no change │
   │ QQuery 2 │   137.51 ms │   133.46 ms │ no change │
   │ QQuery 3 │   159.31 ms │   150.20 ms │ +1.06x faster │
   │ QQuery 4 │  1114.41 ms │  1126.40 ms │ no change │
   │ QQuery 5 │  1357.08 ms │  1386.74 ms │ no change │
   │ QQuery 6 │ 1.43 ms │ 1.45 ms │ no change │
   │ QQuery 7 │53.61 ms │54.27 ms │ no change │
   │ QQuery 8 │  1474.17 ms │  1468.98 ms │ no change │
   │ QQuery 9 │  1818.60 ms │  1789.35 ms │ no change │
   │ QQuery 10│   357.03 ms │   353.62 ms │ no change │
   │ QQuery 11│   400.27 ms │   394.83 ms │ no change │
   │ QQuery 12│  1270.13 ms │  1273.58 ms │ no change │
   │ QQuery 13│  1969.54 ms │  1953.45 ms │ no change │
   │ QQuery 14│  1259.80 ms │  1245.24 ms │ no change │
   │ QQuery 15│  1272.31 ms │  1221.68 ms │ no change │
   │ QQuery 16│  2573.32 ms │  2591.69 ms │ no change │
   │ QQuery 17│  2535.10 ms │  2579.22 ms │ no change │
   │ QQuery 18│  5445.15 ms │  5005.38 ms │ +1.09x faster │
   │ QQuery 19│   123.16 ms │   121.03 ms │ no change │
   │ QQuery 20│  1933.61 ms │  1888.59 ms │ no change │
   │ QQuery 21│  2115.66 ms │  2211.40 ms │ no change │
   │ QQuery 22│  3720.38 ms │  3756.81 ms │ no change │
   │ QQuery 23│ 22330.25 ms │ 12098.87 ms │ +1.85x faster │
   │ QQuery 24│   213.70 ms │   209.57 ms │ no change │
   │ QQuery 25│   456.72 ms │   463.82 ms │ no change │
   │ QQuery 26│   217.99 ms │   206.74 ms │ +1.05x faster │
   │ QQuery 27│  2849.58 ms │  2672.49 ms │ +1.07x faster │
   │ QQuery 28│ 22643.07 ms │ 23254.82 ms │ no change │
   │ QQuery 29│  1003.18 ms │   965.96 ms │ no change │
   │ QQuery 30│  1337.18 ms │  1317.95 ms │ no change │
   │ QQuery 31│  1362.68 ms │  1337.85 ms │ no change │
   │ QQuery 32│  5349.86 ms │  4728.39 ms │ +1.13x faster │
   │ QQuery 33│  5896.39 ms │  5499.63 ms │ +1.07x faster │
   │ QQuery 34│  5921.03 ms │  5651.70 ms │ no change │
   │ QQuery 35│  1954.84 ms │  1860.00 ms │ no change │
   │ QQuery 36│64.52 ms │65.88 ms │ no change │
   │ QQuery 37│44.40 ms │43.29 ms │ no change │
   │ QQuery 38│65.27 ms │65.04 ms │ no change │
   │ QQuery 39│   101.86 ms │99.54 ms │ no change │
   │ QQuery 40│24.38 ms │24.85 ms │ no change │
   │ QQuery 41│22.19 ms │21.72 ms │ no change │
   │ QQuery 42│19.30 ms │19.20 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳━┓
   ┃ Benchmark Summary ┃ ┃
   ┡━━━╇━┩
   │ Total Time (HEAD) │ 103021.02ms │
   │ Total Time (perfect_hj)   │  91364.01ms │
   │ Average Time (HEAD)   │   2395.84ms │
   │

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3728022461

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (c772070b6690093fc094644b618e52bd414c70a9) to 
1037f0aa205e0d04ade7aa9973b4b4c485b696ab 
[diff](https://github.com/apache/datafusion/compare/1037f0aa205e0d04ade7aa9973b4b4c485b696ab..c772070b6690093fc094644b618e52bd414c70a9)
 using:  tpch_mem clickbench_partitioned clickbench_extended
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3727828861

   run benchmark tpch


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-09 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3727828403

   run benchmarks


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-08 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2672460238


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   Agreed. Setting it to ~15% works well—it not only improves performance but 
also reduces the memory footprint (space usage). I've updated the threshold.
   
   ```
   Memory Comparison Matrix (num_rows = 100)
   | Density | Dup Rate | ArrayMap (MB) | JoinHashMap (MB) | Ratio (AM/JHM) |
   |-|--|---|--||
   ...
   | 15% |   0% | 25.43 |37.81 |   0.67x |
   | 15% |  25% | 29.25 |37.81 |   0.77x |
   | 15% |  50% | 29.25 |37.81 |   0.77x |
   | 15% |  75% | 29.25 |37.81 |   0.77x |
   
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-08 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2672453954


##
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##
@@ -168,6 +249,34 @@ impl JoinLeftData {
 /// ` != `) are known as "filter expressions" and are evaluated
 /// after the equijoin predicates.
 ///
+/// # ArrayMap Optimization
+///
+/// For joins with a single integer-based join key, `HashJoinExec` may use an 
[`ArrayMap`]
+/// (also known as a "perfect hash join") instead of a general-purpose hash 
map.
+/// This optimization is used when:
+/// 1. There is exactly one join key.
+/// 2. The join key can be any integer type convertible to u64 (excluding i128 
and u128).

Review Comment:
I've applied the suggested change



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-08 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2672451547


##
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##
@@ -1601,10 +1778,37 @@ mod tests {
 
 #[template]
 #[rstest]
-fn batch_sizes(#[values(8192, 10, 5, 2, 1)] batch_size: usize) {}
+fn hash_join_exec_configs(
+#[values(8192, 10, 5, 2, 1)] batch_size: usize,
+#[values(true, false)] use_perfect_hash_join_as_possible: bool,
+) {
+}
 
-fn prepare_task_ctx(batch_size: usize) -> Arc {
-let session_config = 
SessionConfig::default().with_batch_size(batch_size);
+fn prepare_task_ctx(
+batch_size: usize,
+use_perfect_hash_join_as_possible: bool,
+) -> Arc {
+let mut session_config = 
SessionConfig::default().with_batch_size(batch_size);
+
+if use_perfect_hash_join_as_possible {
+session_config
+.options_mut()
+.execution
+.perfect_hash_join_small_build_threshold = 819200;
+session_config
+.options_mut()
+.execution
+.perfect_hash_join_min_key_density = 0.0;
+} else {
+session_config
+.options_mut()
+.execution
+.perfect_hash_join_small_build_threshold = 0;
+session_config
+.options_mut()
+.execution
+.perfect_hash_join_min_key_density = 1.0 / 0.0;

Review Comment:
   Accepted. Using f64::INFINITY is indeed much clearer.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-08 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2672449674


##
datafusion/physical-plan/src/joins/array_map.rs:
##
@@ -0,0 +1,540 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow_schema::DataType;
+use num_traits::AsPrimitive;
+use std::mem::size_of;
+
+use crate::joins::MapOffset;
+use crate::joins::chain::traverse_chain;
+use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
+use arrow::buffer::BooleanBuffer;
+use arrow::datatypes::ArrowNumericType;
+use datafusion_common::{Result, ScalarValue, internal_err};
+
+/// A macro to downcast only supported integer types (up to 64-bit) and invoke 
a generic function.
+///
+/// Usage: `downcast_supported_integer!(data_type => (Method, arg1, arg2, 
...))`
+///
+/// The `Method` must be an associated method of [`ArrayMap`] that is generic 
over
+/// `` and allow `T::Native: AsPrimitive`.
+macro_rules! downcast_supported_integer {
+($DATA_TYPE:expr => ($METHOD:ident $(, $ARGS:expr)*)) => {
+match $DATA_TYPE {
+arrow::datatypes::DataType::Int8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int64 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt64 => 
ArrayMap::$METHOD::($($ARGS),*),
+_ => {
+return internal_err!(
+"Unsupported type for ArrayMap: {:?}",
+$DATA_TYPE
+);
+}
+}
+};
+}
+
+/// A dense map for single-column integer join keys within a limited range.
+///
+/// Maps join keys to build-side indices using direct array indexing:
+/// `data[val - min_val_in_build_side] -> val_idx_in_build_side + 1`.
+///
+/// NULL values are ignored on both the build side and the probe side.
+///
+/// # Handling Negative Numbers with `wrapping_sub`
+///
+/// This implementation supports signed integer ranges (e.g., `[-5, 5]`) 
efficiently by
+/// treating them as `u64` (Two's Complement) and relying on the bitwise 
properties of
+/// wrapping arithmetic (`wrapping_sub`).
+///
+/// In Two's Complement representation, `a_signed - b_signed` produces the 
same bit pattern
+/// as `a_unsigned.wrapping_sub(b_unsigned)` (modulo 2^N). This allows us to 
perform
+/// range calculations and zero-based index mapping uniformly for both signed 
and unsigned
+/// types without branching.
+///
+/// ## Examples
+///
+/// Consider an `Int64` range `[-5, 5]`.
+/// * `min_val (-5)` casts to `u64`: `...1011` (`u64::MAX - 4`)
+/// * `max_val (5)` casts to `u64`: `...0101` (`5`)
+///
+/// **1. Range Calculation**
+///
+/// ```text
+/// In modular arithmetic, this is equivalent to:
+///   (5 - (2^64 - 5)) mod 2^64
+/// = (5 - 2^64 + 5) mod 2^64
+/// = (10 - 2^64) mod 2^64
+/// = 10
+///
+/// ```
+/// The resulting `range` (10) correctly represents the size of the interval 
`[-5, 5]`.
+///
+/// **2. Index Lookup (in `get_matched_indices`)**
+///
+/// For a probe value of `0` (which is stored as `0u64`):
+/// ```text
+/// In modular arithmetic, this is equivalent to:
+///   (0 - (2^64 - 5)) mod 2^64
+/// = (-2^64 + 5) mod 2^64
+/// = 5
+/// ```
+/// This correctly maps `-5` to index `0`, `0` to index `5`, etc.
+#[derive(Debug)]
+pub struct ArrayMap {
+// data[probSideVal-offset] -> valIdxInBuildSide + 1; 0 for absent
+data: Vec,
+// min val in buildSide
+offset: u64,
+// next[buildSideIdx] -> next matching valIdxInBuildSide + 1; 0 for end of 
chain.
+// If next is empty, it means there are no duplicate keys (no conflicts).
+// It uses the same chain-based conflict resolution as [`JoinHashMapType`].
+next: Vec,
+num_of_distinct_key: usize,
+}
+
+impl ArrayMap {
+pub fn is_supported_type(data_type: &Data

Re: [PR] perfect hash join [datafusion]

2026-01-08 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2672448148


##
datafusion/physical-plan/src/joins/array_map.rs:
##
@@ -0,0 +1,540 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow_schema::DataType;
+use num_traits::AsPrimitive;
+use std::mem::size_of;
+
+use crate::joins::MapOffset;
+use crate::joins::chain::traverse_chain;
+use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
+use arrow::buffer::BooleanBuffer;
+use arrow::datatypes::ArrowNumericType;
+use datafusion_common::{Result, ScalarValue, internal_err};
+
+/// A macro to downcast only supported integer types (up to 64-bit) and invoke 
a generic function.
+///
+/// Usage: `downcast_supported_integer!(data_type => (Method, arg1, arg2, 
...))`
+///
+/// The `Method` must be an associated method of [`ArrayMap`] that is generic 
over
+/// `` and allow `T::Native: AsPrimitive`.
+macro_rules! downcast_supported_integer {
+($DATA_TYPE:expr => ($METHOD:ident $(, $ARGS:expr)*)) => {
+match $DATA_TYPE {
+arrow::datatypes::DataType::Int8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int64 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt64 => 
ArrayMap::$METHOD::($($ARGS),*),
+_ => {
+return internal_err!(
+"Unsupported type for ArrayMap: {:?}",
+$DATA_TYPE
+);
+}
+}
+};
+}
+
+/// A dense map for single-column integer join keys within a limited range.
+///
+/// Maps join keys to build-side indices using direct array indexing:
+/// `data[val - min_val_in_build_side] -> val_idx_in_build_side + 1`.
+///
+/// NULL values are ignored on both the build side and the probe side.
+///
+/// # Handling Negative Numbers with `wrapping_sub`
+///
+/// This implementation supports signed integer ranges (e.g., `[-5, 5]`) 
efficiently by
+/// treating them as `u64` (Two's Complement) and relying on the bitwise 
properties of
+/// wrapping arithmetic (`wrapping_sub`).
+///
+/// In Two's Complement representation, `a_signed - b_signed` produces the 
same bit pattern
+/// as `a_unsigned.wrapping_sub(b_unsigned)` (modulo 2^N). This allows us to 
perform
+/// range calculations and zero-based index mapping uniformly for both signed 
and unsigned
+/// types without branching.
+///
+/// ## Examples
+///
+/// Consider an `Int64` range `[-5, 5]`.
+/// * `min_val (-5)` casts to `u64`: `...1011` (`u64::MAX - 4`)
+/// * `max_val (5)` casts to `u64`: `...0101` (`5`)
+///
+/// **1. Range Calculation**
+///
+/// ```text
+/// In modular arithmetic, this is equivalent to:
+///   (5 - (2^64 - 5)) mod 2^64
+/// = (5 - 2^64 + 5) mod 2^64
+/// = (10 - 2^64) mod 2^64
+/// = 10
+///
+/// ```
+/// The resulting `range` (10) correctly represents the size of the interval 
`[-5, 5]`.
+///
+/// **2. Index Lookup (in `get_matched_indices`)**
+///
+/// For a probe value of `0` (which is stored as `0u64`):
+/// ```text
+/// In modular arithmetic, this is equivalent to:
+///   (0 - (2^64 - 5)) mod 2^64
+/// = (-2^64 + 5) mod 2^64
+/// = 5
+/// ```
+/// This correctly maps `-5` to index `0`, `0` to index `5`, etc.
+#[derive(Debug)]
+pub struct ArrayMap {
+// data[probSideVal-offset] -> valIdxInBuildSide + 1; 0 for absent
+data: Vec,
+// min val in buildSide
+offset: u64,
+// next[buildSideIdx] -> next matching valIdxInBuildSide + 1; 0 for end of 
chain.
+// If next is empty, it means there are no duplicate keys (no conflicts).
+// It uses the same chain-based conflict resolution as [`JoinHashMapType`].
+next: Vec,
+num_of_distinct_key: usize,
+}
+
+impl ArrayMap {
+pub fn is_supported_type(data_type: &Data

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2668825491


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   What about ~15%?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2668825491


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   What about ~0.15?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Copilot commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2668300012


##
datafusion/physical-plan/src/joins/hash_join/exec.rs:
##
@@ -168,6 +249,34 @@ impl JoinLeftData {
 /// ` != `) are known as "filter expressions" and are evaluated
 /// after the equijoin predicates.
 ///
+/// # ArrayMap Optimization
+///
+/// For joins with a single integer-based join key, `HashJoinExec` may use an 
[`ArrayMap`]
+/// (also known as a "perfect hash join") instead of a general-purpose hash 
map.
+/// This optimization is used when:
+/// 1. There is exactly one join key.
+/// 2. The join key can be any integer type convertible to u64 (excluding i128 
and u128).

Review Comment:
   The documentation refers to "excluding i128 and u128" types, but these types 
are not actually checked or handled anywhere in the code. The 
`is_supported_type` function in `array_map.rs` only supports up to 64-bit 
integers (Int8-Int64, UInt8-UInt64). Consider removing the mention of i128/u128 
from the documentation or clarifying that they're not supported due to design 
limitations, not just current implementation.
   ```suggestion
   /// 2. The join key is an integer type up to 64 bits wide that can be 
losslessly converted
   ///to `u64` (128-bit integer types such as `i128` and `u128` are not 
supported).
   ```



##
datafusion/physical-plan/src/joins/array_map.rs:
##
@@ -0,0 +1,540 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow_schema::DataType;
+use num_traits::AsPrimitive;
+use std::mem::size_of;
+
+use crate::joins::MapOffset;
+use crate::joins::chain::traverse_chain;
+use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
+use arrow::buffer::BooleanBuffer;
+use arrow::datatypes::ArrowNumericType;
+use datafusion_common::{Result, ScalarValue, internal_err};
+
+/// A macro to downcast only supported integer types (up to 64-bit) and invoke 
a generic function.
+///
+/// Usage: `downcast_supported_integer!(data_type => (Method, arg1, arg2, 
...))`
+///
+/// The `Method` must be an associated method of [`ArrayMap`] that is generic 
over
+/// `` and allow `T::Native: AsPrimitive`.
+macro_rules! downcast_supported_integer {
+($DATA_TYPE:expr => ($METHOD:ident $(, $ARGS:expr)*)) => {
+match $DATA_TYPE {
+arrow::datatypes::DataType::Int8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::Int64 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt8 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt16 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt32 => 
ArrayMap::$METHOD::($($ARGS),*),
+arrow::datatypes::DataType::UInt64 => 
ArrayMap::$METHOD::($($ARGS),*),
+_ => {
+return internal_err!(
+"Unsupported type for ArrayMap: {:?}",
+$DATA_TYPE
+);
+}
+}
+};
+}
+
+/// A dense map for single-column integer join keys within a limited range.
+///
+/// Maps join keys to build-side indices using direct array indexing:
+/// `data[val - min_val_in_build_side] -> val_idx_in_build_side + 1`.
+///
+/// NULL values are ignored on both the build side and the probe side.
+///
+/// # Handling Negative Numbers with `wrapping_sub`
+///
+/// This implementation supports signed integer ranges (e.g., `[-5, 5]`) 
efficiently by
+/// treating them as `u64` (Two's Complement) and relying on the bitwise 
properties of
+/// wrapping arithmetic (`wrapping_sub`).
+///
+/// In Two's Complement representation, `a_signed - b_signed` produces the 
same bit pattern
+/// as `a_unsigned.wrapping_sub(b_unsigned)` (modulo 2^N). This allows us to 
perform
+/// range calculations and zero-based index mapping uniformly for both signed 
and unsigned
+/// types without branching.
+///
+/// ## Examples
+///
+/// Consider an `Int64` range `[-5, 5]`.
+/// * `min_val (-5)` casts to `u64`: `...1011` (`

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718680693

   🤖 Hi @Dandandan, thanks for the request 
(https://github.com/apache/datafusion/pull/19411#issuecomment-3718680622).
   
   
[`scrape_comments.py`](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/scrape_comments.py)
 only supports whitelisted benchmarks.
   - Standard: clickbench_1, clickbench_extended, clickbench_partitioned, 
clickbench_pushdown, external_aggr, tpcds, tpch, tpch10, tpch_mem, tpch_mem10
   - Criterion: aggregate_query_sql, aggregate_vectorized, case_when, 
character_length, in_list, range_and_generate_series, sort, sql_planner, 
strpos, substr_index, with_hashes
   
   Please choose one or more of these with `run benchmark ` or `run 
benchmark  ...`
   Unsupported benchmarks: hj.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718680622

   run benchmark hj


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718354201

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (e9b35e5ac9e764eeab29aa6ea237e400647466d7) to 
1037f0aa205e0d04ade7aa9973b4b4c485b696ab 
[diff](https://github.com/apache/datafusion/compare/1037f0aa205e0d04ade7aa9973b4b4c485b696ab..e9b35e5ac9e764eeab29aa6ea237e400647466d7)
 using:  tpch
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718372339

   ```
   ┏━━┳━━━┳┳━━━┓
   ┃ Query┃  HEAD ┃ perfect_hj ┃Change ┃
   ┡━━╇━━━╇╇━━━┩
   │ QQuery 1 │ 120.09 ms │  112.47 ms │ +1.07x faster │
   │ QQuery 2 │  29.95 ms │   25.31 ms │ +1.18x faster │
   │ QQuery 3 │  36.86 ms │   36.60 ms │ no change │
   │ QQuery 4 │  28.68 ms │   29.61 ms │ no change │
   │ QQuery 5 │  85.84 ms │   86.63 ms │ no change │
   │ QQuery 6 │  19.61 ms │   19.47 ms │ no change │
   │ QQuery 7 │ 243.13 ms │  145.00 ms │ +1.68x faster │
   │ QQuery 8 │  37.03 ms │   31.49 ms │ +1.18x faster │
   │ QQuery 9 │ 117.04 ms │   95.96 ms │ +1.22x faster │
   │ QQuery 10│  75.18 ms │   63.06 ms │ +1.19x faster │
   │ QQuery 11│  19.93 ms │   12.30 ms │ +1.62x faster │
   │ QQuery 12│  49.38 ms │   49.85 ms │ no change │
   │ QQuery 13│  46.20 ms │   45.37 ms │ no change │
   │ QQuery 14│  13.04 ms │   13.40 ms │ no change │
   │ QQuery 15│  23.47 ms │   23.69 ms │ no change │
   │ QQuery 16│  24.37 ms │   23.86 ms │ no change │
   │ QQuery 17│ 148.67 ms │  147.84 ms │ no change │
   │ QQuery 18│ 284.66 ms │  272.35 ms │ no change │
   │ QQuery 19│  35.58 ms │   37.97 ms │  1.07x slower │
   │ QQuery 20│  48.85 ms │   51.08 ms │ no change │
   │ QQuery 21│ 295.14 ms │  184.30 ms │ +1.60x faster │
   │ QQuery 22│  17.43 ms │   17.36 ms │ no change │
   └──┴───┴┴───┘
   ┏━━━┳━━━┓
   ┃ Benchmark Summary ┃   ┃
   ┡━━━╇━━━┩
   │ Total Time (HEAD) │ 1800.12ms │
   │ Total Time (perfect_hj)   │ 1524.97ms │
   │ Average Time (HEAD)   │   81.82ms │
   │ Average Time (perfect_hj) │   69.32ms │
   │ Queries Faster│ 8 │
   │ Queries Slower│ 1 │
   │ Queries with No Change│13 │
   │ Queries with Failure  │ 0 │
   └───┴───┘
   
   ```
   
   Very nice!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718356562

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (e9b35e5ac9e764eeab29aa6ea237e400647466d7) to 
1037f0aa205e0d04ade7aa9973b4b4c485b696ab 
[diff](https://github.com/apache/datafusion/compare/1037f0aa205e0d04ade7aa9973b4b4c485b696ab..e9b35e5ac9e764eeab29aa6ea237e400647466d7)
 using:  tpcds
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718356620

   Benchmark script failed with exit code 1.
   
   Last 10 lines of output:
   Click to expand
   
   ```
   BRANCH_NAME: HEAD
   DATA_DIR: /home/alamb/arrow-datafusion/benchmarks/data
   RESULTS_DIR: /home/alamb/arrow-datafusion/benchmarks/results/HEAD
   CARGO_COMMAND: cargo run --release
   PREFER_HASH_JOIN: true
   ***
   
   Please prepare TPC-DS data first by following instructions:
 ./bench.sh data tpcds
   ```
   
   
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718356441

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark tpch_sf1.json
   
   ┏━━┳━━━┳┳━━━┓
   ┃ Query┃  HEAD ┃ perfect_hj ┃Change ┃
   ┡━━╇━━━╇╇━━━┩
   │ QQuery 1 │ 191.42 ms │  194.17 ms │ no change │
   │ QQuery 2 │  92.90 ms │   79.24 ms │ +1.17x faster │
   │ QQuery 3 │ 122.93 ms │  118.45 ms │ no change │
   │ QQuery 4 │  76.58 ms │   76.39 ms │ no change │
   │ QQuery 5 │ 169.79 ms │  167.60 ms │ no change │
   │ QQuery 6 │  65.74 ms │   62.99 ms │ no change │
   │ QQuery 7 │ 213.34 ms │  204.62 ms │ no change │
   │ QQuery 8 │ 159.39 ms │  158.60 ms │ no change │
   │ QQuery 9 │ 224.42 ms │  220.08 ms │ no change │
   │ QQuery 10│ 184.10 ms │  187.50 ms │ no change │
   │ QQuery 11│  73.24 ms │   57.11 ms │ +1.28x faster │
   │ QQuery 12│ 116.93 ms │  116.71 ms │ no change │
   │ QQuery 13│ 218.62 ms │  214.30 ms │ no change │
   │ QQuery 14│  94.08 ms │   89.32 ms │ +1.05x faster │
   │ QQuery 15│ 115.42 ms │  117.40 ms │ no change │
   │ QQuery 16│  55.32 ms │   56.42 ms │ no change │
   │ QQuery 17│ 269.67 ms │  269.94 ms │ no change │
   │ QQuery 18│ 318.44 ms │  316.34 ms │ no change │
   │ QQuery 19│ 131.59 ms │  133.16 ms │ no change │
   │ QQuery 20│ 121.70 ms │  124.62 ms │ no change │
   │ QQuery 21│ 259.46 ms │  252.28 ms │ no change │
   │ QQuery 22│  41.13 ms │   36.72 ms │ +1.12x faster │
   └──┴───┴┴───┘
   ┏━━━┳━━━┓
   ┃ Benchmark Summary ┃   ┃
   ┡━━━╇━━━┩
   │ Total Time (HEAD) │ 3316.23ms │
   │ Total Time (perfect_hj)   │ 3253.95ms │
   │ Average Time (HEAD)   │  150.74ms │
   │ Average Time (perfect_hj) │  147.91ms │
   │ Queries Faster│ 4 │
   │ Queries Slower│ 0 │
   │ Queries with No Change│18 │
   │ Queries with Failure  │ 0 │
   └───┴───┘
   ```
   
   
   
   
   
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718353932

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark clickbench_extended.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │  2361.73 ms │  2300.54 ms │ no change │
   │ QQuery 1 │   934.19 ms │   912.49 ms │ no change │
   │ QQuery 2 │  1885.10 ms │  1860.90 ms │ no change │
   │ QQuery 3 │  1202.09 ms │  1180.71 ms │ no change │
   │ QQuery 4 │  2306.91 ms │  2298.40 ms │ no change │
   │ QQuery 5 │ 28041.32 ms │ 28094.82 ms │ no change │
   │ QQuery 6 │  3849.98 ms │  3872.67 ms │ no change │
   │ QQuery 7 │  3794.60 ms │  3815.13 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳┓
   ┃ Benchmark Summary ┃┃
   ┡━━━╇┩
   │ Total Time (HEAD) │ 44375.93ms │
   │ Total Time (perfect_hj)   │ 44335.67ms │
   │ Average Time (HEAD)   │  5546.99ms │
   │ Average Time (perfect_hj) │  5541.96ms │
   │ Queries Faster│  0 │
   │ Queries Slower│  0 │
   │ Queries with No Change│  8 │
   │ Queries with Failure  │  0 │
   └───┴┘
   
   Benchmark clickbench_partitioned.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │ 1.44 ms │ 1.46 ms │ no change │
   │ QQuery 1 │48.94 ms │49.13 ms │ no change │
   │ QQuery 2 │   131.83 ms │   132.88 ms │ no change │
   │ QQuery 3 │   154.94 ms │   151.89 ms │ no change │
   │ QQuery 4 │  1129.27 ms │  1094.93 ms │ no change │
   │ QQuery 5 │  1364.06 ms │  1368.14 ms │ no change │
   │ QQuery 6 │ 1.41 ms │ 1.42 ms │ no change │
   │ QQuery 7 │52.53 ms │53.49 ms │ no change │
   │ QQuery 8 │  1469.70 ms │  1415.32 ms │ no change │
   │ QQuery 9 │  1804.95 ms │  1800.38 ms │ no change │
   │ QQuery 10│   344.22 ms │   345.91 ms │ no change │
   │ QQuery 11│   387.44 ms │   396.02 ms │ no change │
   │ QQuery 12│  1237.81 ms │  1286.77 ms │ no change │
   │ QQuery 13│  1912.18 ms │  1972.25 ms │ no change │
   │ QQuery 14│  1233.69 ms │  1247.50 ms │ no change │
   │ QQuery 15│  1254.11 ms │  1243.60 ms │ no change │
   │ QQuery 16│  2567.98 ms │  2570.61 ms │ no change │
   │ QQuery 17│  2550.81 ms │  2580.33 ms │ no change │
   │ QQuery 18│  5612.71 ms │  4913.15 ms │ +1.14x faster │
   │ QQuery 19│   120.74 ms │   119.55 ms │ no change │
   │ QQuery 20│  1913.07 ms │  1904.79 ms │ no change │
   │ QQuery 21│  2146.63 ms │  2192.36 ms │ no change │
   │ QQuery 22│  3703.55 ms │  3729.43 ms │ no change │
   │ QQuery 23│ 22049.38 ms │ 12242.00 ms │ +1.80x faster │
   │ QQuery 24│   207.87 ms │   203.23 ms │ no change │
   │ QQuery 25│   456.99 ms │   469.41 ms │ no change │
   │ QQuery 26│   214.05 ms │   204.73 ms │ no change │
   │ QQuery 27│  2767.10 ms │  2680.87 ms │ no change │
   │ QQuery 28│ 22195.62 ms │ 23141.30 ms │ no change │
   │ QQuery 29│   991.32 ms │   939.56 ms │ +1.06x faster │
   │ QQuery 30│  1349.48 ms │  1319.89 ms │ no change │
   │ QQuery 31│  1368.06 ms │  1339.89 ms │ no change │
   │ QQuery 32│  5091.91 ms │  5138.39 ms │ no change │
   │ QQuery 33│  5512.57 ms │  5484.79 ms │ no change │
   │ QQuery 34│  5638.93 ms │  6020.19 ms │  1.07x slower │
   │ QQuery 35│  1992.03 ms │  1922.04 ms │ no change │
   │ QQuery 36│63.99 ms │64.41 ms │ no change │
   │ QQuery 37│43.36 ms │45.51 ms │ no change │
   │ QQuery 38│66.10 ms │64.66 ms │ no change │
   │ QQuery 39│   100.63 ms │   101.04 ms │ no change │
   │ QQuery 40│28.11 ms │26.02 ms │ +1.08x faster │
   │ QQuery 41│21.33 ms │22.12 ms │ no change │
   │ QQuery 42│18.14 ms │19.02 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳━┓
   ┃ Benchmark Summary ┃ ┃
   ┡━━━╇━┩
   │ Total Time (HEAD) │ 101320.99ms │
   │ Total Time (perfect_hj)   │  92020.38ms │
   │ Average Time (HEAD)   │   2356.30ms │
   │ Average Time (perfect_hj) │   2140.01ms │
   │ Q

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718215175

   run benchmark tpcds


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718214577

   run benchmark tpch


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718214414

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (e9b35e5ac9e764eeab29aa6ea237e400647466d7) to 
1037f0aa205e0d04ade7aa9973b4b4c485b696ab 
[diff](https://github.com/apache/datafusion/compare/1037f0aa205e0d04ade7aa9973b4b4c485b696ab..e9b35e5ac9e764eeab29aa6ea237e400647466d7)
 using:  tpch_mem clickbench_partitioned clickbench_extended
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718214064

   run benchmarks


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-07 Thread via GitHub



UBarney commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3718078855

   > > > Can you solve the conflicts?
   > > 
   > > 
   > > I've resolved the conflicts. Once #19602 is merged, I will update 
`ArrayMap::mark_existing_probes` to follow logic similar to 
`JoinHashMapType::contain_hashes`.
   > 
   > Done
   
   I have added contain_keys to ArrayMap and updated the logic accordingly.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-06 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3714076071

   > > Can you solve the conflicts?
   > 
   > I've resolved the conflicts. Once #19602 is merged, I will update 
`ArrayMap::mark_existing_probes` to follow logic similar to 
`JoinHashMapType::contain_hashes`.
   
   DonE


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-06 Thread via GitHub



UBarney commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3713987665

   > Can you solve the conflicts?
   
   
   
   I've resolved the conflicts. Once 
https://github.com/apache/datafusion/pull/19602 is merged, I will update 
`ArrayMap::mark_existing_probes` to follow logic similar to 
`JoinHashMapType::contain_hashes`.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-05 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2662706360


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   Cool!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2026-01-05 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3711965227

   Can you solve the conflicts?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-30 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2654932168


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   I think we can set it to 20%.
   
   - In terms of memory usage ([run with this 
code](https://github.com/UBarney/datafusion/commit/d901b70347e24a271464aefb64fe08f64d35a652#diff-1e8db68656c3040876f6740d3bc42251f6d1f9de1f5e3c14d257e72b48a0f68dR10):
 ), `ArrayMap` consumes less memory than `JoinHashMap` at a 20% density, even 
with duplicate keys.
   - Based on the hj.rs benchmark(results in the PR description), `ArrayMap` is 
also faster than `JoinHashMap` at 20% density, regardless of whether there are 
duplicate keys.
   
   ```
   Memory Comparison Matrix (num_rows = 100)
   | Density | Dup Rate | ArrayMap (MB) | JoinHashMap (MB) | Ratio (AM/JHM) |
   |-|--|---|--||
   |100% |   0% |  3.81 |37.81 |   0.10x |
   |100% |  25% |  7.63 |37.81 |   0.20x |
   |100% |  50% |  7.63 |37.81 |   0.20x |
   |100% |  75% |  7.63 |37.81 |   0.20x |
   | 75% |   0% |  5.09 |37.81 |   0.13x |
   | 75% |  25% |  8.90 |37.81 |   0.24x |
   | 75% |  50% |  8.90 |37.81 |   0.24x |
   | 75% |  75% |  8.90 |37.81 |   0.24x |
   | 50% |   0% |  7.63 |37.81 |   0.20x |
   | 50% |  25% | 11.44 |37.81 |   0.30x |
   | 50% |  50% | 11.44 |37.81 |   0.30x |
   | 50% |  75% | 11.44 |37.81 |   0.30x |
   | 20% |   0% | 19.07 |37.81 |   0.50x |
   | 20% |  25% | 22.89 |37.81 |   0.61x |
   | 20% |  50% | 22.89 |37.81 |   0.61x |
   | 20% |  75% | 22.89 |37.81 |   0.61x |
   | 10% |   0% | 38.15 |37.81 |   1.01x |
   | 10% |  25% | 41.96 |37.81 |   1.11x |
   | 10% |  50% | 41.96 |37.81 |   1.11x |
   | 10% |  75% | 41.96 |37.81 |   1.11x |
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-30 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2654932168


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   I think we can set it to 20%.
   
   - In terms of memory usage ([run with this 
code](https://github.com/UBarney/datafusion/commit/209c5002d3273e4ad762077d017c35049c9e4d6f#diff-1e8db68656c3040876f6740d3bc42251f6d1f9de1f5e3c14d257e72b48a0f68dR10):
 ), `ArrayMap` consumes less memory than `JoinHashMap` at a 20% density, even 
with duplicate keys.
   - Based on the hj.rs benchmark(results in the PR description), `ArrayMap` is 
also faster than `JoinHashMap` at 20% density, regardless of whether there are 
duplicate keys.
   
   ```
   Memory Comparison Matrix (num_rows = 100)
   | Density | Dup Rate | Distinct |  Range   | ArrayMap (MB) | JoinHashMap 
(MB) | Ratio (AM/JHM) |
   
|-|--|--|--|---|--||
   |100% |   0% |  100 |  100 |  3.81 |
37.81 |   0.10x |
   |100% |  25% |   75 |  100 |  7.63 |
37.81 |   0.20x |
   |100% |  50% |   50 |  100 |  7.63 |
37.81 |   0.20x |
   |100% |  75% |   25 |  100 |  7.63 |
37.81 |   0.20x |
   | 75% |   0% |  100 |  133 |  5.09 |
37.81 |   0.13x |
   | 75% |  25% |   75 |  133 |  8.90 |
37.81 |   0.24x |
   | 75% |  50% |   50 |  133 |  8.90 |
37.81 |   0.24x |
   | 75% |  75% |   25 |  133 |  8.90 |
37.81 |   0.24x |
   | 50% |   0% |  100 |  200 |  7.63 |
37.81 |   0.20x |
   | 50% |  25% |   75 |  200 | 11.44 |
37.81 |   0.30x |
   | 50% |  50% |   50 |  200 | 11.44 |
37.81 |   0.30x |
   | 50% |  75% |   25 |  200 | 11.44 |
37.81 |   0.30x |
   | 20% |   0% |  100 |  500 | 19.07 |
37.81 |   0.50x |
   | 20% |  25% |   75 |  500 | 22.89 |
37.81 |   0.61x |
   | 20% |  50% |   50 |  500 | 22.89 |
37.81 |   0.61x |
   | 20% |  75% |   25 |  500 | 22.89 |
37.81 |   0.61x |
   | 10% |   0% |  100 | 1000 | 38.15 |
37.81 |   1.01x |
   | 10% |  25% |   75 | 1000 | 41.96 |
37.81 |   1.11x |
   | 10% |  50% |   50 | 1000 | 41.96 |
37.81 |   1.11x |
   | 10% |  75% |   25 | 1000 | 41.96 |
37.81 |   1.11x |
   ```



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-28 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2649548041


##
datafusion/physical-plan/src/joins/array_map.rs:
##
@@ -0,0 +1,565 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow::buffer::MutableBuffer;
+use num_traits::AsPrimitive;
+use std::fmt;
+use std::sync::Arc;
+
+use crate::joins::chain::traverse_chain;
+use crate::joins::join_hash_map::JoinHashMapOffset;
+use crate::joins::utils::JoinHashMapType;
+use arrow::array::{Array, ArrayRef, AsArray};
+use arrow::datatypes::DataType;
+use arrow::datatypes::{
+Int8Type, Int16Type, Int32Type, Int64Type, UInt8Type, UInt16Type, 
UInt32Type,
+UInt64Type,
+};
+use datafusion_common::{Result, internal_err};
+
+/// A "perfect" hash map for single-column integer join keys, represented as a 
dense array.
+///
+/// This structure is highly optimized for joins where the keys are integers 
within a limited
+/// range. Instead of calculating hashes, it uses the integer key itself as an 
index into a
+/// `Vec`, achieving O(1) lookup performance.
+///
+/// # NULL Handling
+///
+/// This optimization can be used for joins with 
`NullEquality::NullEqualsNothing` even if the
+/// join keys contain `NULL`s. This is because:
+///
+/// 1. `try_new` (build side): Ignores rows with `NULL` keys when creating the 
map. This is
+///correct as `NULL` keys would not match anything anyway.
+/// 2. `get_matched_indices_with_limit_offset` (probe side): Skips any `NULL` 
keys encountered
+///in the probe side input.
+///
+/// This structure **cannot** be used for joins with 
`NullEquality::NullEqualsNull` if the
+/// build side contains `NULL`s, as it does not have a mechanism to store and 
match `NULL` values.
+#[derive(Debug)]
+pub struct ArrayMap {
+// data[probSideVal-offset] -> valIdxInBuildSide + 1; 0 for absent
+data: Vec,
+offset: u64, // min val in buildSide
+next: Option>,
+}
+
+impl ArrayMap {
+/// Creates a new [`ArrayKV`] from the given array of join keys.
+///
+/// Note: This function processes only the non-null values in the input 
`array`,
+/// effectively ignoring any rows where the key is `NULL`.
+///
+/// TODO: Support `NullEquality::NullEqualsNull` by storing null indices 
in a
+/// separate `Vec` to allow for `NULL=NULL` matching in the future.
+pub(crate) fn try_new(
+array: &ArrayRef,
+offset_val: u64,
+range: usize,
+) -> Result {
+// Initialize with 0 (sentinel for not found)
+let mut data: Vec = vec![0; range];
+let mut next: Option> = None;

Review Comment:
   Done, it's cleaner this way



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-21 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2637851683


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   I ran a quick test on performance (time taken) at different densities, and 
even at a density of 0.1, ArrayMap was still faster than HashMap 🤔. (I haven't 
measured memory usage yet, though.)
   
   ```
   
┏━━┳━━━┳━┳━━━┓
   ┃ Query┃ density=6 ┃ density=0.1 ┃   
 Change ┃
   
┡━━╇━━━╇━╇━━━┩
   │ QQuery 1_density=1_prob_hit=1_25*1.5M│   5.83 ms │ 4.96 ms │ 
+1.18x faster │
   │ QQuery 2_density=0.026_prob_hit=1_25*1.5M│   6.56 ms │ 4.58 ms │ 
+1.43x faster │
   │ QQuery 3_density=1_prob_hit=1_100K*60M   │ 134.90 ms │94.36 ms │ 
+1.43x faster │
   │ QQuery 4_density=1_prob_hit=0.1_100K*60M │ 167.25 ms │   106.93 ms │ 
+1.56x faster │
   │ QQuery 5_density=0.75_prob_hit=1_100K*60M│ 141.52 ms │93.04 ms │ 
+1.52x faster │
   │ QQuery 6_density=0.75_prob_hit=0.1_100K*60M  │ 248.02 ms │   193.13 ms │ 
+1.28x faster │
   │ QQuery 7_density=0.5_prob_hit=1_100K*60M │ 132.51 ms │82.83 ms │ 
+1.60x faster │
   │ QQuery 8_density=0.5_prob_hit=0.1_100K*60M   │ 226.32 ms │   171.06 ms │ 
+1.32x faster │
   │ QQuery 9_density=0.2_prob_hit=1_100K*60M │ 130.31 ms │96.29 ms │ 
+1.35x faster │
   │ QQuery 10_density=0.2_prob_hit=0.1_100K*60M  │ 231.85 ms │   184.09 ms │ 
+1.26x faster │
   │ QQuery 11_density=0.1_prob_hit=1_100K*60M│ 129.65 ms │   105.23 ms │ 
+1.23x faster │
   │ QQuery 12_density=0.1_prob_hit=0.1_100K*60M  │ 235.93 ms │   191.80 ms │ 
+1.23x faster │
   │ QQuery 13_density=0.01_prob_hit=1_100K*60M   │ 128.74 ms │   129.35 ms │   
  no change │
   │ QQuery 14_density=0.01_prob_hit=0.1_100K*60M │ 230.82 ms │   233.62 ms │   
  no change │
   
└──┴───┴─┴───┘
   ┏┳━━━┓
   ┃ Benchmark Summary  ┃   ┃
   ┡╇━━━┩
   │ Total Time (density=6) │ 2150.21ms │
   │ Total Time (density=0.1)   │ 1691.27ms │
   │ Average Time (density=6)   │  153.59ms │
   │ Average Time (density=0.1) │  120.80ms │
   │ Queries Faster │12 │
   │ Queries Slower │ 0 │
   │ Queries with No Change │ 2 │
   │ Queries with Failure   │ 0 │
   └┴───┘
   ```
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-21 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2637856134


##
benchmarks/compare.py:
##
@@ -154,17 +154,17 @@ def compare(
 baseline = BenchmarkRun.load_from_file(baseline_path)
 comparison = BenchmarkRun.load_from_file(comparison_path)
 
-console = Console()
+console = Console(width=200)

Review Comment:
   I've increased the console width to 200. I added more information like 
'density' to the queryName, which made it longer and caused it to be cut off in 
the output before



##
benchmarks/compare.py:
##
@@ -154,17 +154,17 @@ def compare(
 baseline = BenchmarkRun.load_from_file(baseline_path)
 comparison = BenchmarkRun.load_from_file(comparison_path)
 
-console = Console()
+console = Console(width=200)
 
 # use basename as the column names
-baseline_header = baseline_path.parent.stem
-comparison_header = comparison_path.parent.stem
+baseline_header = baseline_path.parent.name
+comparison_header = comparison_path.parent.name

Review Comment:
   Before, a path like `.../density=0.1/...` was incorrectly shortened to 
`density=0`. Now, by using `.parent.name`, we correctly get the full directory 
name, `density=0.1`



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-20 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2636932448


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   Sounds good!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



UBarney commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2636743834


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   That's a great point. 
   I'll add some benchmarks to compare the performance at different densities, 
including 75%, to find the optimal value for our use case. I'll update this 
based on the results.
   Thanks for the suggestion!
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676314727

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark tpcds_sf1.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 1 │64.32 ms │64.03 ms │ no change │
   │ QQuery 2 │   202.76 ms │   209.93 ms │ no change │
   │ QQuery 3 │   160.17 ms │   160.30 ms │ no change │
   │ QQuery 4 │  2076.33 ms │  2016.14 ms │ no change │
   │ QQuery 5 │   271.72 ms │   267.86 ms │ no change │
   │ QQuery 6 │  1539.80 ms │  1528.76 ms │ no change │
   │ QQuery 7 │   501.34 ms │   500.09 ms │ no change │
   │ QQuery 8 │   172.26 ms │   172.88 ms │ no change │
   │ QQuery 9 │   283.58 ms │   274.82 ms │ no change │
   │ QQuery 10│   169.65 ms │   172.34 ms │ no change │
   │ QQuery 11│  1414.43 ms │  1436.15 ms │ no change │
   │ QQuery 12│74.91 ms │73.81 ms │ no change │
   │ QQuery 13│   554.37 ms │   557.49 ms │ no change │
   │ QQuery 14│  2016.91 ms │  1803.46 ms │ +1.12x faster │
   │ QQuery 15│28.50 ms │27.30 ms │ no change │
   │ QQuery 16│56.60 ms │57.60 ms │ no change │
   │ QQuery 17│   354.64 ms │   357.88 ms │ no change │
   │ QQuery 18│   191.69 ms │   190.50 ms │ no change │
   │ QQuery 19│   228.28 ms │   229.67 ms │ no change │
   │ QQuery 20│23.36 ms │23.50 ms │ no change │
   │ QQuery 21│33.71 ms │32.15 ms │ no change │
   │ QQuery 22│   985.29 ms │   906.05 ms │ +1.09x faster │
   │ QQuery 23│  1845.20 ms │  1713.30 ms │ +1.08x faster │
   │ QQuery 24│   642.89 ms │   636.64 ms │ no change │
   │ QQuery 25│   523.12 ms │   516.07 ms │ no change │
   │ QQuery 26│   123.94 ms │   126.15 ms │ no change │
   │ QQuery 27│   504.93 ms │   500.48 ms │ no change │
   │ QQuery 28│   303.81 ms │   302.04 ms │ no change │
   │ QQuery 29│   444.98 ms │   447.70 ms │ no change │
   │ QQuery 30│65.01 ms │63.94 ms │ no change │
   │ QQuery 31│   306.15 ms │   306.66 ms │ no change │
   │ QQuery 32│77.86 ms │78.00 ms │ no change │
   │ QQuery 33│   193.25 ms │   194.57 ms │ no change │
   │ QQuery 34│   159.04 ms │   162.10 ms │ no change │
   │ QQuery 35│   169.34 ms │   171.45 ms │ no change │
   │ QQuery 36│   296.09 ms │   286.26 ms │ no change │
   │ QQuery 37│   257.06 ms │   254.49 ms │ no change │
   │ QQuery 38│   155.26 ms │   151.49 ms │ no change │
   │ QQuery 39│   216.46 ms │   194.61 ms │ +1.11x faster │
   │ QQuery 40│   197.40 ms │   172.47 ms │ +1.14x faster │
   │ QQuery 41│16.30 ms │16.66 ms │ no change │
   │ QQuery 42│   142.70 ms │   145.52 ms │ no change │
   │ QQuery 43│   126.26 ms │   129.13 ms │ no change │
   │ QQuery 44│15.68 ms │14.96 ms │ no change │
   │ QQuery 45│83.14 ms │80.86 ms │ no change │
   │ QQuery 46│   329.53 ms │   329.04 ms │ no change │
   │ QQuery 47│  1279.95 ms │  1186.17 ms │ +1.08x faster │
   │ QQuery 48│   416.35 ms │   420.97 ms │ no change │
   │ QQuery 49│   355.14 ms │   354.37 ms │ no change │
   │ QQuery 50│   338.48 ms │   343.17 ms │ no change │
   │ QQuery 51│   298.83 ms │   294.59 ms │ no change │
   │ QQuery 52│   147.14 ms │   143.27 ms │ no change │
   │ QQuery 53│   149.53 ms │   146.40 ms │ no change │
   │ QQuery 54│   207.43 ms │   216.19 ms │ no change │
   │ QQuery 55│   144.21 ms │   144.60 ms │ no change │
   │ QQuery 56│   193.16 ms │   190.45 ms │ no change │
   │ QQuery 57│   319.98 ms │   302.28 ms │ +1.06x faster │
   │ QQuery 58│   515.69 ms │   482.75 ms │ +1.07x faster │
   │ QQuery 59│   285.93 ms │   288.57 ms │ no change │
   │ QQuery 60│   199.98 ms │   199.54 ms │ no change │
   │ QQuery 61│   240.08 ms │   235.47 ms │ no change │
   │ QQuery 62│  1378.44 ms │  1398.12 ms │ no change │
   │ QQuery 63│   149.43 ms │   148.88 ms │ no change │
   │ QQuery 64│  1142.94 ms │  1161.26 ms │ no change │
   │ QQuery 65│   368.38 ms │   363.41 ms │ no change │
   │ QQuery 66│   389.40 ms │   393.14 ms │ no change │
   │ QQuery 67│   646.76 ms │   627.61 ms │ no change │
   │ QQuery 68│   383.87 ms │   384.78 ms │ no change │
   │ QQuery 69│   167.41 ms │   170.00 ms │ no change │
   │ QQuery 70│   526.93 ms │   528.35 ms │ no change │
   │ QQuery 71│   183.79 ms │   184.70

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676292704

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (a442460deb5764caf51a454fcc0959292e0cf530) to 
8550010bd55ccae217b08240664c44fa8bda8261 
[diff](https://github.com/apache/datafusion/compare/8550010bd55ccae217b08240664c44fa8bda8261..a442460deb5764caf51a454fcc0959292e0cf530)
 using:  tpcds
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676292478

   🤖: Benchmark completed
   
   Details
   
   
   
   ```
   Comparing HEAD and perfect_hj
   
   Benchmark clickbench_extended.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │  2728.43 ms │  2746.77 ms │ no change │
   │ QQuery 1 │  1259.76 ms │  1286.32 ms │ no change │
   │ QQuery 2 │  2442.97 ms │  2404.14 ms │ no change │
   │ QQuery 3 │  1146.01 ms │  1175.40 ms │ no change │
   │ QQuery 4 │  2324.58 ms │  2297.95 ms │ no change │
   │ QQuery 5 │ 28847.71 ms │ 28651.86 ms │ no change │
   │ QQuery 6 │  3925.44 ms │  4071.92 ms │ no change │
   │ QQuery 7 │  3480.92 ms │  3513.25 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳┓
   ┃ Benchmark Summary ┃┃
   ┡━━━╇┩
   │ Total Time (HEAD) │ 46155.84ms │
   │ Total Time (perfect_hj)   │ 46147.61ms │
   │ Average Time (HEAD)   │  5769.48ms │
   │ Average Time (perfect_hj) │  5768.45ms │
   │ Queries Faster│  0 │
   │ Queries Slower│  0 │
   │ Queries with No Change│  8 │
   │ Queries with Failure  │  0 │
   └───┴┘
   
   Benchmark clickbench_partitioned.json
   
   ┏━━┳━┳━┳━━━┓
   ┃ Query┃HEAD ┃  perfect_hj ┃Change ┃
   ┡━━╇━╇━╇━━━┩
   │ QQuery 0 │ 2.55 ms │ 2.28 ms │ +1.12x faster │
   │ QQuery 1 │49.94 ms │49.72 ms │ no change │
   │ QQuery 2 │   136.75 ms │   135.77 ms │ no change │
   │ QQuery 3 │   157.55 ms │   156.38 ms │ no change │
   │ QQuery 4 │  1127.59 ms │  1099.95 ms │ no change │
   │ QQuery 5 │  1513.28 ms │  1540.48 ms │ no change │
   │ QQuery 6 │ 2.09 ms │ 2.18 ms │ no change │
   │ QQuery 7 │54.92 ms │54.54 ms │ no change │
   │ QQuery 8 │  1435.36 ms │  1429.02 ms │ no change │
   │ QQuery 9 │  1826.50 ms │  1818.96 ms │ no change │
   │ QQuery 10│   362.05 ms │   359.18 ms │ no change │
   │ QQuery 11│   413.64 ms │   415.45 ms │ no change │
   │ QQuery 12│  1346.02 ms │  1355.55 ms │ no change │
   │ QQuery 13│  2003.64 ms │  2030.93 ms │ no change │
   │ QQuery 14│  1258.62 ms │  1264.24 ms │ no change │
   │ QQuery 15│  1236.44 ms │  1220.63 ms │ no change │
   │ QQuery 16│  2660.06 ms │  2679.40 ms │ no change │
   │ QQuery 17│  2646.48 ms │  2669.57 ms │ no change │
   │ QQuery 18│  5032.89 ms │  5243.53 ms │ no change │
   │ QQuery 19│   119.08 ms │   120.08 ms │ no change │
   │ QQuery 20│  1909.83 ms │  1955.97 ms │ no change │
   │ QQuery 21│  2219.56 ms │  2228.45 ms │ no change │
   │ QQuery 22│  3754.10 ms │  3742.17 ms │ no change │
   │ QQuery 23│ 12284.83 ms │ 12304.70 ms │ no change │
   │ QQuery 24│   200.89 ms │   216.80 ms │  1.08x slower │
   │ QQuery 25│   459.79 ms │   477.52 ms │ no change │
   │ QQuery 26│   217.46 ms │   226.68 ms │ no change │
   │ QQuery 27│  2733.98 ms │  2714.81 ms │ no change │
   │ QQuery 28│ 24706.02 ms │ 23446.26 ms │ +1.05x faster │
   │ QQuery 29│   983.86 ms │   951.63 ms │ no change │
   │ QQuery 30│  1325.66 ms │  1334.96 ms │ no change │
   │ QQuery 31│  1361.59 ms │  1319.42 ms │ no change │
   │ QQuery 32│  4654.91 ms │  4894.57 ms │  1.05x slower │
   │ QQuery 33│  5895.01 ms │  5580.74 ms │ +1.06x faster │
   │ QQuery 34│  5921.45 ms │  5968.72 ms │ no change │
   │ QQuery 35│  1944.76 ms │  1894.39 ms │ no change │
   │ QQuery 36│66.49 ms │65.88 ms │ no change │
   │ QQuery 37│45.71 ms │47.05 ms │ no change │
   │ QQuery 38│66.55 ms │67.85 ms │ no change │
   │ QQuery 39│   105.16 ms │   104.80 ms │ no change │
   │ QQuery 40│28.03 ms │27.95 ms │ no change │
   │ QQuery 41│23.88 ms │24.08 ms │ no change │
   │ QQuery 42│19.99 ms │20.73 ms │ no change │
   └──┴─┴─┴───┘
   ┏━━━┳┓
   ┃ Benchmark Summary ┃┃
   ┡━━━╇┩
   │ Total Time (HEAD) │ 94314.96ms │
   │ Total Time (perfect_hj)   │ 93263.97ms │
   │ Average Time (HEAD)   │  2193.37ms │
   │ Average Time (perfect_hj) │  2168.93ms │
   │ Queries

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2636002211


##
datafusion/common/src/config.rs:
##
@@ -468,6 +468,25 @@ config_namespace! {
 /// metadata memory consumption
 pub batch_size: usize, default = 8192
 
+/// A perfect hash join will be considered if the number of rows on 
the build
+/// side is below this threshold. This provides a fast path for joins 
with
+/// very small build sides, bypassing the density check.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_small_build_threshold: usize, default = 1024
+
+/// The minimum required density of join keys on the build side to 
consider a
+/// perfect hash join. Density is calculated as:
+/// `(number of rows) / (max_key - min_key + 1)`.
+/// A perfect hash join may be used if the actual key density exceeds 
this
+/// value. For example, a value of 0.99 means the keys must fill at 
least
+/// 99% of their value range.
+/// 
+/// TODO: Currently only supports cases where left_side.num_rows() < 
u32::MAX.
+/// Support for left_side.num_rows() >= u32::MAX will be added in the 
future.
+pub perfect_hash_join_min_key_density: f64, default = 0.99

Review Comment:
   This seems very high? For a hashmap I believe it's ~75% default (plus it has 
some more overhead per key), so I think a 75% probably could still be better 
overall?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676159917

   run benchmark tpcds


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



alamb-ghbot commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676159863

   🤖 `./gh_compare_branch.sh` 
[gh_compare_branch.sh](https://github.com/alamb/datafusion-benchmarking/blob/main/scripts/gh_compare_branch.sh)
 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 perfect_hj (a442460deb5764caf51a454fcc0959292e0cf530) to 
8550010bd55ccae217b08240664c44fa8bda8261 
[diff](https://github.com/apache/datafusion/compare/8550010bd55ccae217b08240664c44fa8bda8261..a442460deb5764caf51a454fcc0959292e0cf530)
 using:  tpch_mem clickbench_partitioned clickbench_extended
   Results will be posted here when complete
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



Dandandan commented on PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#issuecomment-3676159501

   run benchmarks


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Re: [PR] perfect hash join [datafusion]

2025-12-19 Thread via GitHub



Dandandan commented on code in PR #19411:
URL: https://github.com/apache/datafusion/pull/19411#discussion_r2635957210


##
datafusion/physical-plan/src/joins/array_map.rs:
##
@@ -0,0 +1,565 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow::buffer::MutableBuffer;
+use num_traits::AsPrimitive;
+use std::fmt;
+use std::sync::Arc;
+
+use crate::joins::chain::traverse_chain;
+use crate::joins::join_hash_map::JoinHashMapOffset;
+use crate::joins::utils::JoinHashMapType;
+use arrow::array::{Array, ArrayRef, AsArray};
+use arrow::datatypes::DataType;
+use arrow::datatypes::{
+Int8Type, Int16Type, Int32Type, Int64Type, UInt8Type, UInt16Type, 
UInt32Type,
+UInt64Type,
+};
+use datafusion_common::{Result, internal_err};
+
+/// A "perfect" hash map for single-column integer join keys, represented as a 
dense array.
+///
+/// This structure is highly optimized for joins where the keys are integers 
within a limited
+/// range. Instead of calculating hashes, it uses the integer key itself as an 
index into a
+/// `Vec`, achieving O(1) lookup performance.
+///
+/// # NULL Handling
+///
+/// This optimization can be used for joins with 
`NullEquality::NullEqualsNothing` even if the
+/// join keys contain `NULL`s. This is because:
+///
+/// 1. `try_new` (build side): Ignores rows with `NULL` keys when creating the 
map. This is
+///correct as `NULL` keys would not match anything anyway.
+/// 2. `get_matched_indices_with_limit_offset` (probe side): Skips any `NULL` 
keys encountered
+///in the probe side input.
+///
+/// This structure **cannot** be used for joins with 
`NullEquality::NullEqualsNull` if the
+/// build side contains `NULL`s, as it does not have a mechanism to store and 
match `NULL` values.
+#[derive(Debug)]
+pub struct ArrayMap {
+// data[probSideVal-offset] -> valIdxInBuildSide + 1; 0 for absent
+data: Vec,
+offset: u64, // min val in buildSide
+next: Option>,
+}
+
+impl ArrayMap {
+/// Creates a new [`ArrayKV`] from the given array of join keys.
+///
+/// Note: This function processes only the non-null values in the input 
`array`,
+/// effectively ignoring any rows where the key is `NULL`.
+///
+/// TODO: Support `NullEquality::NullEqualsNull` by storing null indices 
in a
+/// separate `Vec` to allow for `NULL=NULL` matching in the future.
+pub(crate) fn try_new(
+array: &ArrayRef,
+offset_val: u64,
+range: usize,
+) -> Result {
+// Initialize with 0 (sentinel for not found)
+let mut data: Vec = vec![0; range];
+let mut next: Option> = None;

Review Comment:
   ```suggestion
   let mut next: Vec = vec![];
   ```
   
   I think this should work as well



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

48 matches

Mail list logo