Skip to content

Commit 0fcb9ab

Browse files
CuteChuanChuanOmega359
authored andcommitted
fix: count each probe row once in HashJoinExec probe_hit_rate and avg_fanout (apache#25272)
## Which issue does this PR close? - Closes apache#25077 . ## Rationale for this change `EXPLAIN ANALYZE` reports `probe_hit_rate` and `avg_fanout` of `HashJoinExec` too low whenever a probe batch produces more than `batch_size` output rows, e.g. when the build side has many duplicate keys. Both metrics are defined per probe row, but their counters were updated once per output chunk. ## What changes are included in this PR? - `probe_hit_rate` total: added only on the first chunk of each probe batch (`state.offset == (0, None)`), the same first-chunk check that `process_probe_batch` already uses for correlated null-aware `LeftMark`. - `probe_hit_rate` part and `avg_fanout` total: a new `ProcessProbeBatchState::matched_probe_idx` records the last probe index counted so far. `count_new_matched_probe_rows` does not count a chunk's first index again if it equals that value. Empty chunks leave it unchanged. - Existing state is not reused: `joined_probe_idx` is tracked after the join filter, while these metrics are defined before it, and the lookup `offset` can point at a probe row that has not been counted yet. ## What is the testing strategy for this PR? Two new tests in `hash_join/exec.rs`, each run over `hash_join_exec_configs` (batch sizes 8192/10/5/2/1, perfect hash join on and off): - `join_probe_metrics_count_each_probe_row_once`: duplicate build keys, so one probe row's matches are split across chunks. Fails without this change for batch sizes 5, 2 and 1. - `join_probe_metrics_count_probe_row_starting_new_chunk`: unique build keys, so chunks split between probe rows. It guards against deduplicating by the lookup offset: comparing against `offset.0` (on non-first chunks) instead makes this test fail for batch sizes 2 and 1, while the first test still passes. ## Are there any user-facing changes? `probe_hit_rate` and `avg_fanout` shown by `EXPLAIN ANALYZE` are now correct when a probe batch is processed in several chunks. No public API changes.
1 parent a95806f commit 0fcb9ab

2 files changed

Lines changed: 175 additions & 8 deletions

File tree

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

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3145,6 +3145,25 @@ mod tests {
31453145
}
31463146
}
31473147

3148+
#[track_caller]
3149+
fn assert_ratio_metric(
3150+
metrics: &MetricsSet,
3151+
metric_name: &str,
3152+
expected_part: usize,
3153+
expected_total: usize,
3154+
) {
3155+
let Some(MetricValue::Ratio { ratio_metrics, .. }) =
3156+
metrics.sum_by_name(metric_name)
3157+
else {
3158+
panic!("should have {metric_name} metrics")
3159+
};
3160+
assert_eq!(
3161+
(ratio_metrics.part(), ratio_metrics.total()),
3162+
(expected_part, expected_total),
3163+
"{metric_name} (part, total) mismatch",
3164+
);
3165+
}
3166+
31483167
fn build_schema_and_on() -> Result<(SchemaRef, SchemaRef, JoinOn)> {
31493168
let left_schema = Arc::new(Schema::new(vec![
31503169
Field::new("a1", DataType::Int32, true),
@@ -3191,6 +3210,7 @@ mod tests {
31913210
use datafusion_physical_expr::{
31923211
EquivalenceProperties, PhysicalSortExpr, RangePartitioning, SplitPoint,
31933212
};
3213+
use datafusion_physical_expr_common::metrics::MetricValue;
31943214
use futures::StreamExt;
31953215
use hashbrown::HashTable;
31963216
use insta::{allow_duplicates, assert_snapshot};
@@ -4197,6 +4217,128 @@ mod tests {
41974217
TestMemoryExec::try_new_exec(&[vec![batch.clone(), batch]], schema, None).unwrap()
41984218
}
41994219

4220+
/// `probe_hit_rate` and `avg_fanout` must count each probe row once, even
4221+
/// when a probe batch is processed in several chunks. Every probe row matches
4222+
/// all 3 build rows, so any `batch_size` below 9 splits the probe batch into
4223+
/// chunks, and some splits cut a single row's matches across chunks.
4224+
#[apply(hash_join_exec_configs)]
4225+
#[tokio::test]
4226+
async fn join_probe_metrics_count_each_probe_row_once(
4227+
batch_size: usize,
4228+
use_perfect_hash_join_as_possible: bool,
4229+
) -> Result<()> {
4230+
let task_ctx = prepare_task_ctx(batch_size, use_perfect_hash_join_as_possible);
4231+
let left = build_table(
4232+
("a1", &vec![1, 2, 3]),
4233+
("b1", &vec![2, 2, 2]),
4234+
("c1", &vec![3, 4, 5]),
4235+
);
4236+
let right = build_table(
4237+
("a2", &vec![10, 20, 30]),
4238+
("b1", &vec![2, 2, 2]),
4239+
("c2", &vec![30, 40, 50]),
4240+
);
4241+
let on = vec![(
4242+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
4243+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
4244+
)];
4245+
4246+
let (columns, batches, metrics) = join_collect(
4247+
Arc::clone(&left),
4248+
Arc::clone(&right),
4249+
on.clone(),
4250+
&JoinType::Inner,
4251+
NullEquality::NullEqualsNothing,
4252+
task_ctx,
4253+
)
4254+
.await?;
4255+
4256+
assert_eq!(columns, vec!["a1", "b1", "c1", "a2", "b1", "c2"]);
4257+
allow_duplicates! {
4258+
assert_snapshot!(batches_to_string(&batches), @r"
4259+
+----+----+----+----+----+----+
4260+
| a1 | b1 | c1 | a2 | b1 | c2 |
4261+
+----+----+----+----+----+----+
4262+
| 1 | 2 | 3 | 10 | 2 | 30 |
4263+
| 2 | 2 | 4 | 10 | 2 | 30 |
4264+
| 3 | 2 | 5 | 10 | 2 | 30 |
4265+
| 1 | 2 | 3 | 20 | 2 | 40 |
4266+
| 2 | 2 | 4 | 20 | 2 | 40 |
4267+
| 3 | 2 | 5 | 20 | 2 | 40 |
4268+
| 1 | 2 | 3 | 30 | 2 | 50 |
4269+
| 2 | 2 | 4 | 30 | 2 | 50 |
4270+
| 3 | 2 | 5 | 30 | 2 | 50 |
4271+
+----+----+----+----+----+----+
4272+
");
4273+
}
4274+
4275+
assert_join_metrics!(metrics, 9);
4276+
assert_phj_used(&metrics, use_perfect_hash_join_as_possible);
4277+
4278+
assert_ratio_metric(&metrics, "probe_hit_rate", 3, 3);
4279+
assert_ratio_metric(&metrics, "avg_fanout", 9, 3);
4280+
4281+
Ok(())
4282+
}
4283+
4284+
/// Complements `join_probe_metrics_count_each_probe_row_once`: with unique
4285+
/// build keys each probe row has at most one match, so chunks always split
4286+
/// between probe rows. A probe row that starts a new chunk must still be
4287+
/// counted, even though the lookup offset already points at it.
4288+
#[apply(hash_join_exec_configs)]
4289+
#[tokio::test]
4290+
async fn join_probe_metrics_count_probe_row_starting_new_chunk(
4291+
batch_size: usize,
4292+
use_perfect_hash_join_as_possible: bool,
4293+
) -> Result<()> {
4294+
let task_ctx = prepare_task_ctx(batch_size, use_perfect_hash_join_as_possible);
4295+
let left = build_table(
4296+
("a1", &vec![1, 2, 3]),
4297+
("b1", &vec![4, 5, 6]),
4298+
("c1", &vec![7, 8, 9]),
4299+
);
4300+
let right = build_table(
4301+
("a2", &vec![10, 20, 25, 30]),
4302+
("b1", &vec![4, 4, 4, 40]),
4303+
("c2", &vec![70, 80, 85, 90]),
4304+
);
4305+
let on = vec![(
4306+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
4307+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
4308+
)];
4309+
4310+
let (columns, batches, metrics) = join_collect(
4311+
Arc::clone(&left),
4312+
Arc::clone(&right),
4313+
on.clone(),
4314+
&JoinType::Inner,
4315+
NullEquality::NullEqualsNothing,
4316+
task_ctx,
4317+
)
4318+
.await?;
4319+
4320+
assert_eq!(columns, vec!["a1", "b1", "c1", "a2", "b1", "c2"]);
4321+
allow_duplicates! {
4322+
assert_snapshot!(batches_to_string(&batches), @"
4323+
+----+----+----+----+----+----+
4324+
| a1 | b1 | c1 | a2 | b1 | c2 |
4325+
+----+----+----+----+----+----+
4326+
| 1 | 4 | 7 | 10 | 4 | 70 |
4327+
| 1 | 4 | 7 | 20 | 4 | 80 |
4328+
| 1 | 4 | 7 | 25 | 4 | 85 |
4329+
+----+----+----+----+----+----+
4330+
");
4331+
}
4332+
4333+
assert_join_metrics!(metrics, 3);
4334+
assert_phj_used(&metrics, use_perfect_hash_join_as_possible);
4335+
4336+
assert_ratio_metric(&metrics, "probe_hit_rate", 3, 4);
4337+
assert_ratio_metric(&metrics, "avg_fanout", 3, 3);
4338+
4339+
Ok(())
4340+
}
4341+
42004342
#[apply(hash_join_exec_configs)]
42014343
#[tokio::test]
42024344
async fn join_left_multi_batch(

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

Lines changed: 33 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -188,6 +188,11 @@ pub(super) struct ProcessProbeBatchState {
188188
offset: MapOffset,
189189
/// Max joined probe-side index from current batch
190190
joined_probe_idx: Option<usize>,
191+
/// Max probe-side index with a join-key match from current batch, before
192+
/// the join filter is applied (unlike `joined_probe_idx`). Lets
193+
/// `probe_hit_rate` and `avg_fanout` count a probe row whose matches span
194+
/// several chunks only once.
195+
matched_probe_idx: Option<u32>,
191196
}
192197

193198
impl ProcessProbeBatchState {
@@ -197,6 +202,23 @@ impl ProcessProbeBatchState {
197202
self.joined_probe_idx = joined_probe_idx;
198203
}
199204
}
205+
206+
/// Returns how many probe rows in `right_indices`, the join-key matches of
207+
/// the current chunk, have not been counted by a previous chunk of this
208+
/// probe batch, and records the last matched index in `matched_probe_idx`.
209+
fn count_new_matched_probe_rows(&mut self, right_indices: &UInt32Array) -> usize {
210+
let values = right_indices.values();
211+
let mut count = count_distinct_sorted_indices(right_indices);
212+
// A probe row whose matches span a chunk boundary is the last index of the
213+
// previous chunk and the first index of this one; count it only once.
214+
if let (Some(&first), Some(&last)) = (values.first(), values.last()) {
215+
if Some(first) == self.matched_probe_idx {
216+
count -= 1;
217+
}
218+
self.matched_probe_idx = Some(last);
219+
}
220+
count
221+
}
200222
}
201223

202224
/// Container for HashJoinStreamState::EmitUnmatchedBuildRows related data
@@ -786,6 +808,7 @@ impl HashJoinStream {
786808
valid_keys,
787809
offset: (0, None),
788810
joined_probe_idx: None,
811+
matched_probe_idx: None,
789812
});
790813
}
791814
Some(Err(err)) => return Poll::Ready(Err(err)),
@@ -803,9 +826,13 @@ impl HashJoinStream {
803826
let state = self.state.try_as_process_probe_batch_mut()?;
804827
let build_side = self.build_side.try_as_ready_mut()?;
805828

806-
self.join_metrics
807-
.probe_hit_rate
808-
.add_total(state.batch.num_rows());
829+
// A probe batch may be processed in several chunks; count its rows once,
830+
// on the first chunked lookup (offset == (0, None)).
831+
if state.offset == (0, None) {
832+
self.join_metrics
833+
.probe_hit_rate
834+
.add_total(state.batch.num_rows());
835+
}
809836

810837
let timer = self.join_metrics.join_time.timer();
811838

@@ -890,17 +917,15 @@ impl HashJoinStream {
890917
}
891918
};
892919

893-
let distinct_right_indices_count = count_distinct_sorted_indices(&right_indices);
920+
let matched_probe_rows = state.count_new_matched_probe_rows(&right_indices);
894921

895922
self.join_metrics
896923
.probe_hit_rate
897-
.add_part(distinct_right_indices_count);
924+
.add_part(matched_probe_rows);
898925

899926
self.join_metrics.avg_fanout.add_part(left_indices.len());
900927

901-
self.join_metrics
902-
.avg_fanout
903-
.add_total(distinct_right_indices_count);
928+
self.join_metrics.avg_fanout.add_total(matched_probe_rows);
904929

905930
// apply join filter if exists
906931
let (left_indices, right_indices) = if let Some(filter) = &self.filter {

0 commit comments

Comments
 (0)