You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "buraksenn (via GitHub)" <gi...@apache.org> on 2026/03/12 12:46:38 UTC
[PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
buraksenn opened a new pull request, #20904:
URL: https://github.com/apache/datafusion/pull/20904
## Which issue does this PR close?
Does not close but part of https://github.com/apache/datafusion/issues/20766
## Rationale for this change
Details are in #20766. But main idea is to use existing distinct count information to optimize joins similar to how Spark/Trino does
## What changes are included in this PR?
This PR extends cardinality estimation for semi/anti joins using distinct counts
## Are these changes tested?
I've added cases but not sure if I should've added benchmarks on this.
## Are there any user-facing changes?
No
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286764315
run benchmarks tpcds 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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930525523
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,88 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+///
+/// PostgreSQL uses a similar approach in `eqjoinsel_semi`
+/// (`src/backend/utils/adt/selfuncs.c`). When NDV statistics are
+/// available on both sides it computes selectivity as `nd2 / nd1`,
+/// which is equivalent to `min(outer_ndv, inner_ndv) / outer_ndv`.
+/// If either side lacks statistics it falls back to a default.
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+ let inner_rows = *inner_num_rows.get_value()?;
+ if inner_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_selectivity_estimate = false;
+
+ for (outer_stat, inner_stat) in outer_col_stats.iter().zip(inner_col_stats.iter()) {
+ let outer_has_stats = outer_stat.distinct_count.get_value().is_some()
+ || (outer_stat.min_value.get_value().is_some()
+ && outer_stat.max_value.get_value().is_some());
+ let inner_has_stats = inner_stat.distinct_count.get_value().is_some()
+ || (inner_stat.min_value.get_value().is_some()
+ && inner_stat.max_value.get_value().is_some());
+ if !outer_has_stats || !inner_has_stats {
+ continue;
+ }
+
+ let outer_ndv = max_distinct_count(outer_num_rows, outer_stat);
+ let inner_ndv = max_distinct_count(inner_num_rows, inner_stat);
+
+ if let (Some(&o), Some(&i)) = (outer_ndv.get_value(), inner_ndv.get_value())
+ && o > 0
+ {
+ selectivity *= (o.min(i) as f64) / (o as f64);
Review Comment:
I took a look at the Postgres' implementation (the branch without the "most common values", which we don't track), I noticed a potential improvement over what we have now.
Postgres uses `selec = min(1, inner_ndv/outer_ndv) * (1 - nullfrac)` as core formula ([code is here](https://github.com/postgres/postgres/blob/f30cebb9542358702ca0f2c4be2cd504a2568606/src/backend/utils/adt/selfuncs.c#L2872) I have "condensed" the if/else into a single formula and renamed the variables `ndv1 -> outer_ndv` and `ndv2 -> inner_ndv`, so it's clear, but it's equivalent to the code).
We use `selec = min(inner_ndv, outer_ndv) / outer_ndv` (renamed again for readability here), which is equivalent to Postgres' `min(1, inner_ndv/outer_ndv)`.
We don't account for `NULL` values, we are missing the `* (1 - nullfrac)` part of their formula.
Postgres removes them, as `NULL` values cannot ever match, and we could do that too, when `ColumnStatistics::null_count` is available.
We could do it this way:
```suggestion
let null_frac = outer_stat.null_count
.get_value()
.map(|&nc| nc as f64 / outer_rows as f64)
.unwrap_or(0.0);
selectivity *= (o.min(i) as f64) / (o as f64) * (1.0 - null_frac);
```
WDYT?
If you accept the change, we would need a few additional test cases to exercise this part of the code, I can think of these cases:
- single column with nulls on outer side
- anti-join with nulls
- all outer rows are null
- multi-column with nulls on one column
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286830583
๐ค Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286664748)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and use-ndv-for-semi-and-anti-join
--------------------
Benchmark tpcds_sf1.json
--------------------
โโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโ
โ Query โ HEAD โ use-ndv-for-semi-and-anti-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 6.15 / 6.55 ยฑ0.72 / 7.99 ms โ 6.17 / 6.64 ยฑ0.81 / 8.25 ms โ no change โ
โ QQuery 2 โ 112.57 / 113.13 ยฑ0.71 / 114.50 ms โ 111.60 / 123.11 ยฑ20.21 / 163.46 ms โ 1.09x slower โ
โ QQuery 3 โ 108.82 / 109.50 ยฑ0.69 / 110.83 ms โ 108.99 / 110.03 ยฑ0.60 / 110.82 ms โ no change โ
โ QQuery 4 โ 1039.25 / 1068.91 ยฑ16.19 / 1085.14 ms โ 1039.20 / 1059.08 ยฑ13.72 / 1074.81 ms โ no change โ
โ QQuery 5 โ 191.03 / 194.29 ยฑ2.37 / 198.33 ms โ 193.57 / 197.86 ยฑ3.46 / 202.10 ms โ no change โ
โ QQuery 6 โ 240.05 / 253.01 ยฑ7.65 / 263.22 ms โ 250.53 / 256.69 ยฑ7.61 / 271.10 ms โ no change โ
โ QQuery 7 โ 335.94 / 339.65 ยฑ3.10 / 343.33 ms โ 329.72 / 336.88 ยฑ5.21 / 345.77 ms โ no change โ
โ QQuery 8 โ 155.31 / 162.03 ยฑ5.23 / 170.94 ms โ 154.49 / 163.78 ยฑ4.73 / 167.71 ms โ no change โ
โ QQuery 9 โ 231.94 / 244.74 ยฑ7.23 / 253.29 ms โ 202.44 / 232.73 ยฑ17.86 / 257.46 ms โ no change โ
โ QQuery 10 โ 168.67 / 173.73 ยฑ4.03 / 179.79 ms โ 170.80 / 175.60 ยฑ3.93 / 180.12 ms โ no change โ
โ QQuery 11 โ 696.40 / 705.47 ยฑ9.70 / 721.59 ms โ 687.33 / 698.19 ยฑ6.94 / 708.54 ms โ no change โ
โ QQuery 12 โ 37.83 / 39.73 ยฑ1.58 / 42.22 ms โ 38.72 / 40.03 ยฑ1.68 / 43.35 ms โ no change โ
โ QQuery 13 โ 554.84 / 564.74 ยฑ8.11 / 572.50 ms โ 540.40 / 559.24 ยฑ13.66 / 574.98 ms โ no change โ
โ QQuery 14 โ 900.79 / 909.28 ยฑ9.25 / 926.53 ms โ 910.47 / 918.66 ยฑ5.94 / 927.86 ms โ no change โ
โ QQuery 15 โ 18.91 / 21.84 ยฑ2.20 / 24.40 ms โ 18.89 / 20.28 ยฑ1.49 / 22.93 ms โ +1.08x faster โ
โ QQuery 16 โ 6.71 / 7.10 ยฑ0.32 / 7.48 ms โ 6.82 / 7.23 ยฑ0.28 / 7.62 ms โ no change โ
โ QQuery 17 โ 204.75 / 206.58 ยฑ2.06 / 210.59 ms โ 197.63 / 202.25 ยฑ5.49 / 211.48 ms โ no change โ
โ QQuery 18 โ 382.30 / 415.20 ยฑ34.38 / 476.68 ms โ 424.43 / 481.23 ยฑ32.21 / 514.19 ms โ 1.16x slower โ
โ QQuery 19 โ 141.38 / 145.29 ยฑ2.05 / 147.44 ms โ 144.36 / 144.85 ยฑ0.47 / 145.60 ms โ no change โ
โ QQuery 20 โ 14.98 / 16.95 ยฑ1.18 / 18.19 ms โ 14.37 / 16.19 ยฑ1.16 / 17.96 ms โ no change โ
โ QQuery 21 โ 26.86 / 28.08 ยฑ0.73 / 29.11 ms โ 26.02 / 27.64 ยฑ0.94 / 28.91 ms โ no change โ
โ QQuery 22 โ 497.97 / 505.32 ยฑ4.98 / 511.58 ms โ 502.48 / 508.25 ยฑ3.18 / 511.60 ms โ no change โ
โ QQuery 23 โ 1211.83 / 1218.81 ยฑ4.11 / 1224.08 ms โ 1200.17 / 1211.43 ยฑ6.44 / 1218.22 ms โ no change โ
โ QQuery 24 โ 122.91 / 124.67 ยฑ1.75 / 127.67 ms โ 120.61 / 122.13 ยฑ2.17 / 126.36 ms โ no change โ
โ QQuery 25 โ 293.03 / 302.09 ยฑ7.29 / 311.82 ms โ 295.14 / 296.78 ยฑ1.25 / 298.65 ms โ no change โ
โ QQuery 26 โ 141.27 / 147.20 ยฑ4.80 / 152.46 ms โ 138.93 / 144.44 ยฑ3.47 / 147.93 ms โ no change โ
โ QQuery 27 โ 6.44 / 7.12 ยฑ0.62 / 8.03 ms โ 6.59 / 7.60 ยฑ1.69 / 10.96 ms โ 1.07x slower โ
โ QQuery 28 โ 222.05 / 228.22 ยฑ4.98 / 233.80 ms โ 224.38 / 229.33 ยฑ3.16 / 234.30 ms โ no change โ
โ QQuery 29 โ 245.18 / 252.63 ยฑ3.82 / 255.99 ms โ 248.74 / 252.39 ยฑ3.05 / 255.90 ms โ no change โ
โ QQuery 30 โ 55.15 / 58.82 ยฑ2.11 / 61.50 ms โ 55.79 / 58.07 ยฑ1.65 / 60.60 ms โ no change โ
โ QQuery 31 โ 174.66 / 178.17 ยฑ2.47 / 182.08 ms โ 173.25 / 175.76 ยฑ1.50 / 177.52 ms โ no change โ
โ QQuery 32 โ 13.70 / 14.28 ยฑ0.65 / 15.16 ms โ 13.30 / 14.02 ยฑ0.65 / 15.18 ms โ no change โ
โ QQuery 33 โ 128.59 / 132.35 ยฑ2.51 / 136.04 ms โ 130.53 / 131.72 ยฑ1.27 / 133.46 ms โ no change โ
โ QQuery 34 โ 6.73 / 7.24 ยฑ0.51 / 8.07 ms โ 6.67 / 7.07 ยฑ0.37 / 7.66 ms โ no change โ
โ QQuery 35 โ 140.96 / 145.99 ยฑ2.96 / 149.62 ms โ 148.59 / 149.43 ยฑ0.89 / 151.03 ms โ no change โ
โ QQuery 36 โ 6.10 / 6.42 ยฑ0.33 / 6.99 ms โ 6.22 / 6.46 ยฑ0.23 / 6.82 ms โ no change โ
โ QQuery 37 โ 5.06 / 5.23 ยฑ0.12 / 5.36 ms โ 5.12 / 5.27 ยฑ0.17 / 5.55 ms โ no change โ
โ QQuery 38 โ 105.25 / 107.17 ยฑ1.96 / 110.96 ms โ 120.95 / 123.98 ยฑ2.58 / 127.69 ms โ 1.16x slower โ
โ QQuery 39 โ 131.88 / 136.51 ยฑ2.69 / 139.14 ms โ 135.02 / 138.00 ยฑ2.88 / 143.09 ms โ no change โ
โ QQuery 40 โ 127.87 / 137.53 ยฑ7.11 / 148.76 ms โ 130.45 / 135.30 ยฑ5.64 / 146.34 ms โ no change โ
โ QQuery 41 โ 13.71 / 14.87 ยฑ1.31 / 17.39 ms โ 14.18 / 14.98 ยฑ0.62 / 15.73 ms โ no change โ
โ QQuery 42 โ 113.89 / 116.31 ยฑ2.30 / 119.77 ms โ 108.04 / 112.25 ยฑ2.89 / 116.19 ms โ no change โ
โ QQuery 43 โ 5.36 / 5.59 ยฑ0.27 / 5.99 ms โ 5.46 / 5.61 ยฑ0.16 / 5.81 ms โ no change โ
โ QQuery 44 โ 11.00 / 12.08 ยฑ0.97 / 13.84 ms โ 11.04 / 11.63 ยฑ0.59 / 12.75 ms โ no change โ
โ QQuery 45 โ 42.40 / 45.35 ยฑ1.71 / 47.53 ms โ 42.89 / 46.01 ยฑ2.39 / 49.84 ms โ no change โ
โ QQuery 46 โ 8.15 / 8.24 ยฑ0.10 / 8.39 ms โ 8.20 / 8.63 ยฑ0.25 / 8.94 ms โ no change โ
โ QQuery 47 โ 770.36 / 773.51 ยฑ3.33 / 778.63 ms โ 777.25 / 786.02 ยฑ10.03 / 805.42 ms โ no change โ
โ QQuery 48 โ 473.85 / 486.47 ยฑ7.43 / 495.18 ms โ 479.61 / 486.07 ยฑ4.49 / 493.08 ms โ no change โ
โ QQuery 49 โ 282.85 / 286.81 ยฑ5.34 / 296.89 ms โ 278.60 / 286.90 ยฑ5.09 / 294.61 ms โ no change โ
โ QQuery 50 โ 531.39 / 536.40 ยฑ3.10 / 541.06 ms โ 508.64 / 530.26 ยฑ12.25 / 544.29 ms โ no change โ
โ QQuery 51 โ 220.57 / 222.52 ยฑ2.08 / 226.25 ms โ 214.26 / 217.02 ยฑ2.57 / 221.52 ms โ no change โ
โ QQuery 52 โ 111.37 / 117.07 ยฑ3.12 / 120.87 ms โ 114.24 / 117.26 ยฑ3.72 / 124.46 ms โ no change โ
โ QQuery 53 โ 139.77 / 146.72 ยฑ5.27 / 153.02 ms โ 143.39 / 147.17 ยฑ1.93 / 148.65 ms โ no change โ
โ QQuery 54 โ 126.09 / 130.28 ยฑ2.13 / 131.81 ms โ 128.03 / 131.29 ยฑ2.39 / 134.09 ms โ no change โ
โ QQuery 55 โ 114.63 / 115.40 ยฑ0.51 / 116.18 ms โ 113.90 / 115.50 ยฑ1.03 / 116.68 ms โ no change โ
โ QQuery 56 โ 131.20 / 134.34 ยฑ1.82 / 135.95 ms โ 133.39 / 135.21 ยฑ1.20 / 137.16 ms โ no change โ
โ QQuery 57 โ 187.17 / 189.15 ยฑ1.33 / 190.51 ms โ 187.62 / 188.97 ยฑ0.92 / 190.18 ms โ no change โ
โ QQuery 58 โ 222.90 / 232.70 ยฑ13.68 / 259.45 ms โ 266.45 / 269.46 ยฑ2.02 / 271.86 ms โ 1.16x slower โ
โ QQuery 59 โ 276.92 / 282.59 ยฑ3.74 / 286.75 ms โ 278.83 / 281.37 ยฑ1.72 / 283.63 ms โ no change โ
โ QQuery 60 โ 136.73 / 140.45 ยฑ2.10 / 143.21 ms โ 136.29 / 140.31 ยฑ2.93 / 145.05 ms โ no change โ
โ QQuery 61 โ 11.73 / 12.40 ยฑ0.65 / 13.45 ms โ 11.75 / 12.59 ยฑ0.79 / 13.67 ms โ no change โ
โ QQuery 62 โ 873.89 / 955.85 ยฑ81.38 / 1106.97 ms โ 897.57 / 955.56 ยฑ46.81 / 1018.42 ms โ no change โ
โ QQuery 63 โ 144.49 / 150.98 ยฑ3.84 / 156.47 ms โ 140.67 / 146.34 ยฑ3.25 / 150.47 ms โ no change โ
โ QQuery 64 โ 28431.72 / 29522.36 ยฑ799.79 / 30673.57 ms โ 27917.80 / 29003.42 ยฑ629.70 / 29529.23 ms โ no change โ
โ QQuery 65 โ 365.61 / 370.54 ยฑ3.24 / 373.84 ms โ 355.82 / 366.45 ยฑ6.16 / 372.19 ms โ no change โ
โ QQuery 66 โ 190.29 / 197.83 ยฑ4.55 / 201.74 ms โ 190.81 / 199.89 ยฑ6.34 / 208.42 ms โ no change โ
โ QQuery 67 โ 495.23 / 506.92 ยฑ10.04 / 525.59 ms โ 471.17 / 497.00 ยฑ14.94 / 515.73 ms โ no change โ
โ QQuery 68 โ 9.76 / 11.69 ยฑ1.80 / 14.16 ms โ 8.23 / 11.23 ยฑ1.69 / 13.03 ms โ no change โ
โ QQuery 69 โ 171.48 / 178.27 ยฑ4.22 / 182.29 ms โ 171.24 / 175.49 ยฑ3.39 / 180.81 ms โ no change โ
โ QQuery 70 โ 425.58 / 435.99 ยฑ8.02 / 447.51 ms โ 415.68 / 432.24 ยฑ11.88 / 450.70 ms โ no change โ
โ QQuery 71 โ 130.33 / 132.98 ยฑ2.35 / 136.88 ms โ 127.03 / 132.91 ยฑ3.40 / 137.09 ms โ no change โ
โ QQuery 72 โ 1212.21 / 1242.45 ยฑ15.36 / 1254.73 ms โ 1180.56 / 1189.01 ยฑ5.13 / 1195.45 ms โ no change โ
โ QQuery 73 โ 7.14 / 7.82 ยฑ0.67 / 9.02 ms โ 7.47 / 7.94 ยฑ0.47 / 8.68 ms โ no change โ
โ QQuery 74 โ 502.62 / 511.35 ยฑ4.79 / 516.32 ms โ 483.17 / 496.74 ยฑ8.78 / 509.24 ms โ no change โ
โ QQuery 75 โ 280.63 / 286.96 ยฑ4.26 / 292.08 ms โ 279.75 / 284.87 ยฑ2.84 / 287.26 ms โ no change โ
โ QQuery 76 โ 276.35 / 278.08 ยฑ1.16 / 279.11 ms โ 271.22 / 277.27 ยฑ3.17 / 280.39 ms โ no change โ
โ QQuery 77 โ 230.23 / 232.62 ยฑ2.11 / 235.87 ms โ 231.14 / 232.05 ยฑ0.91 / 233.71 ms โ no change โ
โ QQuery 78 โ 290.48 / 301.19 ยฑ6.22 / 309.41 ms โ 298.35 / 301.98 ยฑ3.92 / 309.61 ms โ no change โ
โ QQuery 79 โ 261.13 / 262.32 ยฑ0.99 / 263.54 ms โ 260.64 / 263.50 ยฑ1.86 / 266.50 ms โ no change โ
โ QQuery 80 โ 284.40 / 285.92 ยฑ1.25 / 287.26 ms โ 283.91 / 285.71 ยฑ1.19 / 287.26 ms โ no change โ
โ QQuery 81 โ 31.37 / 33.18 ยฑ2.54 / 38.21 ms โ 31.27 / 33.04 ยฑ1.95 / 36.83 ms โ no change โ
โ QQuery 82 โ 46.07 / 48.60 ยฑ1.42 / 49.71 ms โ 48.64 / 49.72 ยฑ1.06 / 51.20 ms โ no change โ
โ QQuery 83 โ 44.27 / 45.56 ยฑ1.50 / 48.36 ms โ 44.65 / 45.67 ยฑ1.11 / 47.71 ms โ no change โ
โ QQuery 84 โ 65.51 / 66.10 ยฑ0.71 / 67.45 ms โ 65.33 / 66.11 ยฑ0.42 / 66.53 ms โ no change โ
โ QQuery 85 โ 274.71 / 282.53 ยฑ4.55 / 287.69 ms โ 282.95 / 295.00 ยฑ6.99 / 304.18 ms โ no change โ
โ QQuery 86 โ 47.62 / 50.46 ยฑ2.83 / 54.90 ms โ 49.51 / 50.97 ยฑ0.87 / 52.07 ms โ no change โ
โ QQuery 87 โ 105.59 / 107.48 ยฑ1.87 / 110.51 ms โ 3.47 / 3.63 ยฑ0.26 / 4.14 ms โ +29.62x faster โ
โ QQuery 88 โ 127.66 / 132.89 ยฑ3.58 / 138.10 ms โ 135.54 / 140.83 ยฑ4.47 / 149.11 ms โ 1.06x slower โ
โ QQuery 89 โ 149.58 / 162.22 ยฑ6.56 / 168.35 ms โ 164.05 / 172.94 ยฑ7.63 / 186.40 ms โ 1.07x slower โ
โ QQuery 90 โ 22.94 / 25.05 ยฑ1.42 / 26.50 ms โ 26.99 / 28.59 ยฑ0.95 / 29.67 ms โ 1.14x slower โ
โ QQuery 91 โ 98.77 / 105.49 ยฑ5.88 / 113.94 ms โ 103.94 / 110.26 ยฑ3.23 / 113.12 ms โ no change โ
โ QQuery 92 โ 53.08 / 53.86 ยฑ0.67 / 54.77 ms โ 54.87 / 57.00 ยฑ1.38 / 58.80 ms โ 1.06x slower โ
โ QQuery 93 โ 186.64 / 188.65 ยฑ1.11 / 190.01 ms โ 196.58 / 199.04 ยฑ1.44 / 200.54 ms โ 1.06x slower โ
โ QQuery 94 โ 67.22 / 68.67 ยฑ1.41 / 71.10 ms โ 68.87 / 70.88 ยฑ1.25 / 72.53 ms โ no change โ
โ QQuery 95 โ 144.69 / 147.21 ยฑ1.56 / 149.55 ms โ 143.71 / 148.91 ยฑ3.15 / 152.91 ms โ no change โ
โ QQuery 96 โ 78.21 / 85.24 ยฑ4.06 / 88.74 ms โ 80.83 / 87.93 ยฑ3.77 / 91.35 ms โ no change โ
โ QQuery 97 โ 149.40 / 154.35 ยฑ2.83 / 157.03 ms โ 150.98 / 154.44 ยฑ3.29 / 160.14 ms โ no change โ
โ QQuery 98 โ 125.07 / 126.22 ยฑ1.46 / 129.06 ms โ 122.50 / 125.05 ยฑ2.23 / 128.53 ms โ no change โ
โ QQuery 99 โ 10658.19 / 10710.06 ยฑ27.14 / 10734.49 ms โ 10705.42 / 10732.23 ยฑ23.33 / 10770.96 ms โ no change โ
โโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (HEAD) โ 61916.72ms โ
โ Total Time (use-ndv-for-semi-and-anti-join) โ 61371.94ms โ
โ Average Time (HEAD) โ 625.42ms โ
โ Average Time (use-ndv-for-semi-and-anti-join) โ 619.92ms โ
โ Queries Faster โ 2 โ
โ Queries Slower โ 10 โ
โ Queries with No Change โ 87 โ
โ Queries with Failure โ 0 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpcds โ base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 310.1s |
| Peak memory | 37.6 GiB |
| Avg memory | 26.1 GiB |
| CPU user | 606.8s |
| CPU sys | 27.3s |
| Peak spill | 0 B |
**tpcds โ branch**
| Metric | Value |
|--------|-------|
| Wall time | 310.1s |
| Peak memory | 35.4 GiB |
| Avg memory | 26.0 GiB |
| CPU user | 608.1s |
| CPU sys | 26.5s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 merged PR #20904:
URL: https://github.com/apache/datafusion/pull/20904
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286780960
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286764315)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286764315-1668-84wt4 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpch
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4287508188
Benchmark for [this request](https://github.com/apache/datafusion/pull/20904#issuecomment-4286764315) hit the 7200s job deadline before finishing.
Benchmarks requested: `tpch`
<details><summary>Kubernetes message</summary>
```
Job was active longer than specified deadline
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930523244
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
Review Comment:
Thanks @asolimando I understand and it totally makes sense. I could not find relevant estimation logic for this in Trino maybe I've missed this. Given Postgres approach and reference in comments I think it makes sense to go forward with this.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930071947
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
Review Comment:
No reservations, but I think it's valuable to point to the original implementation for multiple reasons: documentation, revisit the implementation if the original source improves over it, and recognition for the original author/project.
As I said, this looks reasonable and correct to me.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286930570
```
select count(*)
from ((select distinct c_last_name, c_first_name, d_date
from store_sales, date_dim, customer
where store_sales.ss_sold_date_sk = date_dim.d_date_sk
and store_sales.ss_customer_sk = customer.c_customer_sk
and d_month_seq between 1189 and 1189+11)
except
(select distinct c_last_name, c_first_name, d_date
from catalog_sales, date_dim, customer
where catalog_sales.cs_sold_date_sk = date_dim.d_date_sk
and catalog_sales.cs_bill_customer_sk = customer.c_customer_sk
and d_month_seq between 1189 and 1189+11)
except
(select distinct c_last_name, c_first_name, d_date
from web_sales, date_dim, customer
where web_sales.ws_sold_date_sk = date_dim.d_date_sk
and web_sales.ws_bill_customer_sk = customer.c_customer_sk
and d_month_seq between 1189 and 1189+11)
) cool_cust
;
```
I didn't find semi-anti joins for the query. I guess it might be related to the count(*) gets a stat directly
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286802859
๐ค Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and use-ndv-for-semi-and-anti-join
--------------------
Benchmark tpcds_sf1.json
--------------------
โโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโ
โ Query โ HEAD โ use-ndv-for-semi-and-anti-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 6.42 / 6.78 ยฑ0.67 / 8.11 ms โ 6.42 / 6.82 ยฑ0.71 / 8.23 ms โ no change โ
โ QQuery 2 โ 145.82 / 148.54 ยฑ3.64 / 155.69 ms โ 146.56 / 147.19 ยฑ0.56 / 148.21 ms โ no change โ
โ QQuery 3 โ 113.69 / 114.01 ยฑ0.35 / 114.64 ms โ 113.62 / 114.72 ยฑ1.57 / 117.78 ms โ no change โ
โ QQuery 4 โ 1286.53 / 1338.12 ยฑ55.39 / 1445.73 ms โ 1254.43 / 1325.91 ยฑ104.15 / 1530.00 ms โ no change โ
โ QQuery 5 โ 176.74 / 178.24 ยฑ1.56 / 180.85 ms โ 178.65 / 179.58 ยฑ0.63 / 180.30 ms โ no change โ
โ QQuery 6 โ 878.14 / 904.35 ยฑ26.38 / 943.08 ms โ 834.43 / 897.42 ยฑ35.56 / 930.46 ms โ no change โ
โ QQuery 7 โ 341.84 / 344.52 ยฑ4.08 / 352.60 ms โ 343.18 / 344.75 ยฑ1.43 / 347.14 ms โ no change โ
โ QQuery 8 โ 115.65 / 117.21 ยฑ1.02 / 118.35 ms โ 115.51 / 116.94 ยฑ1.04 / 118.46 ms โ no change โ
โ QQuery 9 โ 100.01 / 103.03 ยฑ2.46 / 106.95 ms โ 100.06 / 103.47 ยฑ5.49 / 114.39 ms โ no change โ
โ QQuery 10 โ 104.99 / 106.30 ยฑ1.10 / 108.20 ms โ 104.67 / 106.15 ยฑ1.06 / 107.16 ms โ no change โ
โ QQuery 11 โ 907.29 / 1041.18 ยฑ69.13 / 1097.53 ms โ 909.54 / 932.60 ยฑ12.87 / 946.28 ms โ +1.12x faster โ
โ QQuery 12 โ 47.43 / 49.97 ยฑ1.96 / 52.48 ms โ 44.58 / 47.19 ยฑ2.49 / 51.79 ms โ +1.06x faster โ
โ QQuery 13 โ 404.77 / 418.39 ยฑ10.79 / 428.45 ms โ 396.73 / 402.90 ยฑ4.18 / 407.52 ms โ no change โ
โ QQuery 14 โ 992.80 / 1009.60 ยฑ11.15 / 1025.37 ms โ 998.10 / 1018.35 ยฑ12.92 / 1032.43 ms โ no change โ
โ QQuery 15 โ 14.92 / 15.67 ยฑ0.66 / 16.70 ms โ 17.16 / 18.46 ยฑ0.89 / 19.50 ms โ 1.18x slower โ
โ QQuery 16 โ 6.96 / 7.16 ยฑ0.17 / 7.44 ms โ 7.88 / 8.12 ยฑ0.29 / 8.61 ms โ 1.13x slower โ
โ QQuery 17 โ 226.42 / 228.78 ยฑ1.91 / 232.22 ms โ 239.05 / 241.89 ยฑ2.52 / 245.43 ms โ 1.06x slower โ
โ QQuery 18 โ 128.50 / 130.98 ยฑ1.92 / 133.29 ms โ 132.37 / 133.65 ยฑ1.01 / 135.05 ms โ no change โ
โ QQuery 19 โ 162.40 / 165.34 ยฑ1.79 / 167.75 ms โ 164.26 / 165.44 ยฑ1.27 / 167.62 ms โ no change โ
โ QQuery 20 โ 14.34 / 14.87 ยฑ0.43 / 15.38 ms โ 15.02 / 15.46 ยฑ0.38 / 16.05 ms โ no change โ
โ QQuery 21 โ 20.64 / 21.03 ยฑ0.27 / 21.37 ms โ 20.54 / 21.39 ยฑ0.53 / 22.07 ms โ no change โ
โ QQuery 22 โ 522.64 / 528.24 ยฑ5.11 / 534.44 ms โ 484.35 / 518.11 ยฑ28.09 / 564.95 ms โ no change โ
โ QQuery 23 โ 853.16 / 871.31 ยฑ10.42 / 883.07 ms โ 856.26 / 878.47 ยฑ31.07 / 939.61 ms โ no change โ
โ QQuery 24 โ 377.48 / 380.17 ยฑ1.82 / 382.26 ms โ 405.69 / 409.10 ยฑ3.62 / 415.88 ms โ 1.08x slower โ
โ QQuery 25 โ 338.31 / 340.71 ยฑ1.40 / 342.24 ms โ 356.35 / 357.93 ยฑ0.85 / 358.73 ms โ 1.05x slower โ
โ QQuery 26 โ 79.54 / 81.50 ยฑ1.63 / 84.27 ms โ 86.08 / 87.54 ยฑ0.97 / 89.10 ms โ 1.07x slower โ
โ QQuery 27 โ 6.63 / 7.05 ยฑ0.53 / 8.07 ms โ 7.37 / 7.71 ยฑ0.24 / 8.02 ms โ 1.09x slower โ
โ QQuery 28 โ 147.79 / 149.68 ยฑ2.23 / 153.94 ms โ 153.95 / 155.46 ยฑ1.48 / 158.09 ms โ no change โ
โ QQuery 29 โ 279.63 / 282.07 ยฑ1.98 / 285.04 ms โ 281.77 / 290.57 ยฑ5.02 / 295.50 ms โ no change โ
โ QQuery 30 โ 43.57 / 45.69 ยฑ1.91 / 48.91 ms โ 43.58 / 45.33 ยฑ1.23 / 46.78 ms โ no change โ
โ QQuery 31 โ 178.01 / 179.22 ยฑ1.02 / 180.53 ms โ 170.76 / 173.19 ยฑ1.51 / 175.24 ms โ no change โ
โ QQuery 32 โ 14.27 / 14.47 ยฑ0.14 / 14.71 ms โ 13.20 / 22.58 ยฑ17.00 / 56.56 ms โ 1.56x slower โ
โ QQuery 33 โ 147.48 / 150.86 ยฑ2.41 / 153.59 ms โ 139.55 / 141.69 ยฑ1.20 / 143.20 ms โ +1.06x faster โ
โ QQuery 34 โ 7.66 / 7.77 ยฑ0.08 / 7.90 ms โ 6.84 / 7.02 ยฑ0.23 / 7.45 ms โ +1.11x faster โ
โ QQuery 35 โ 112.80 / 116.42 ยฑ2.00 / 118.33 ms โ 106.28 / 108.27 ยฑ1.32 / 110.15 ms โ +1.08x faster โ
โ QQuery 36 โ 6.97 / 7.33 ยฑ0.22 / 7.62 ms โ 6.37 / 6.53 ยฑ0.18 / 6.76 ms โ +1.12x faster โ
โ QQuery 37 โ 9.43 / 10.23 ยฑ0.83 / 11.82 ms โ 8.70 / 9.33 ยฑ0.71 / 10.67 ms โ +1.10x faster โ
โ QQuery 38 โ 89.05 / 93.22 ยฑ2.64 / 96.80 ms โ 95.53 / 98.85 ยฑ3.72 / 106.06 ms โ 1.06x slower โ
โ QQuery 39 โ 140.51 / 143.36 ยฑ3.79 / 150.87 ms โ 121.73 / 125.61 ยฑ2.78 / 129.53 ms โ +1.14x faster โ
โ QQuery 40 โ 117.06 / 123.14 ยฑ6.35 / 133.25 ms โ 108.48 / 114.59 ยฑ7.58 / 129.13 ms โ +1.07x faster โ
โ QQuery 41 โ 15.41 / 16.82 ยฑ1.03 / 18.17 ms โ 14.26 / 14.92 ยฑ0.44 / 15.42 ms โ +1.13x faster โ
โ QQuery 42 โ 110.26 / 111.65 ยฑ1.43 / 114.31 ms โ 106.45 / 108.38 ยฑ1.09 / 109.83 ms โ no change โ
โ QQuery 43 โ 5.54 / 5.67 ยฑ0.17 / 6.01 ms โ 5.49 / 5.60 ยฑ0.11 / 5.81 ms โ no change โ
โ QQuery 44 โ 11.28 / 11.97 ยฑ0.69 / 13.29 ms โ 11.28 / 11.62 ยฑ0.20 / 11.82 ms โ no change โ
โ QQuery 45 โ 52.11 / 53.38 ยฑ0.92 / 54.92 ms โ 50.71 / 51.52 ยฑ0.65 / 52.57 ms โ no change โ
โ QQuery 46 โ 7.98 / 8.78 ยฑ0.59 / 9.70 ms โ 8.31 / 8.86 ยฑ0.61 / 9.80 ms โ no change โ
โ QQuery 47 โ 691.19 / 706.01 ยฑ11.59 / 719.46 ms โ 698.11 / 792.16 ยฑ68.89 / 860.53 ms โ 1.12x slower โ
โ QQuery 48 โ 286.04 / 289.26 ยฑ1.98 / 291.71 ms โ 297.82 / 307.43 ยฑ6.43 / 316.32 ms โ 1.06x slower โ
โ QQuery 49 โ 252.48 / 255.18 ยฑ2.33 / 258.74 ms โ 252.18 / 253.87 ยฑ1.93 / 257.55 ms โ no change โ
โ QQuery 50 โ 226.69 / 229.52 ยฑ3.16 / 235.52 ms โ 224.81 / 229.74 ยฑ2.66 / 231.88 ms โ no change โ
โ QQuery 51 โ 178.17 / 182.91 ยฑ3.28 / 187.05 ms โ 180.78 / 184.34 ยฑ3.14 / 188.99 ms โ no change โ
โ QQuery 52 โ 108.46 / 110.18 ยฑ1.29 / 112.36 ms โ 107.22 / 108.58 ยฑ1.10 / 110.29 ms โ no change โ
โ QQuery 53 โ 102.46 / 104.31 ยฑ1.78 / 107.21 ms โ 101.38 / 102.83 ยฑ1.39 / 104.80 ms โ no change โ
โ QQuery 54 โ 145.90 / 147.87 ยฑ1.49 / 149.86 ms โ 145.40 / 145.98 ยฑ0.74 / 147.43 ms โ no change โ
โ QQuery 55 โ 107.82 / 109.41 ยฑ1.17 / 110.83 ms โ 105.84 / 108.80 ยฑ2.22 / 112.16 ms โ no change โ
โ QQuery 56 โ 139.59 / 141.83 ยฑ1.45 / 143.68 ms โ 140.03 / 141.70 ยฑ1.33 / 143.78 ms โ no change โ
โ QQuery 57 โ 172.93 / 175.35 ยฑ2.09 / 178.16 ms โ 169.39 / 172.46 ยฑ1.58 / 173.87 ms โ no change โ
โ QQuery 58 โ 270.33 / 273.50 ยฑ2.09 / 275.75 ms โ 316.52 / 318.68 ยฑ2.35 / 322.84 ms โ 1.17x slower โ
โ QQuery 59 โ 196.83 / 197.93 ยฑ0.79 / 199.30 ms โ 196.03 / 198.39 ยฑ2.08 / 200.83 ms โ no change โ
โ QQuery 60 โ 145.37 / 146.94 ยฑ1.40 / 148.77 ms โ 143.24 / 147.51 ยฑ2.64 / 150.75 ms โ no change โ
โ QQuery 61 โ 13.23 / 13.47 ยฑ0.15 / 13.67 ms โ 13.39 / 14.05 ยฑ0.49 / 14.84 ms โ no change โ
โ QQuery 62 โ 956.55 / 987.26 ยฑ21.23 / 1022.58 ms โ 898.28 / 1006.53 ยฑ76.76 / 1127.00 ms โ no change โ
โ QQuery 63 โ 105.45 / 108.14 ยฑ2.54 / 112.74 ms โ 103.15 / 104.81 ยฑ2.52 / 109.80 ms โ no change โ
โ QQuery 64 โ 676.41 / 689.99 ยฑ13.90 / 716.40 ms โ 680.12 / 682.47 ยฑ2.63 / 687.52 ms โ no change โ
โ QQuery 65 โ 252.50 / 253.95 ยฑ1.41 / 256.54 ms โ 251.79 / 253.96 ยฑ1.90 / 257.06 ms โ no change โ
โ QQuery 66 โ 236.56 / 252.53 ยฑ15.55 / 272.07 ms โ 241.15 / 255.27 ยฑ11.41 / 269.74 ms โ no change โ
โ QQuery 67 โ 319.18 / 332.57 ยฑ6.99 / 338.45 ms โ 307.02 / 313.38 ยฑ6.27 / 324.50 ms โ +1.06x faster โ
โ QQuery 68 โ 10.20 / 11.13 ยฑ1.21 / 13.52 ms โ 8.11 / 9.77 ยฑ1.65 / 12.77 ms โ +1.14x faster โ
โ QQuery 69 โ 105.05 / 107.96 ยฑ4.12 / 116.02 ms โ 102.59 / 104.19 ยฑ0.88 / 105.24 ms โ no change โ
โ QQuery 70 โ 353.73 / 365.09 ยฑ10.24 / 382.23 ms โ 341.31 / 347.28 ยฑ6.16 / 358.87 ms โ no change โ
โ QQuery 71 โ 138.72 / 142.80 ยฑ2.99 / 147.05 ms โ 135.56 / 137.19 ยฑ1.34 / 139.31 ms โ no change โ
โ QQuery 72 โ 654.16 / 670.30 ยฑ14.67 / 689.22 ms โ 618.93 / 625.35 ยฑ5.35 / 632.03 ms โ +1.07x faster โ
โ QQuery 73 โ 7.14 / 8.01 ยฑ0.61 / 8.93 ms โ 6.84 / 7.91 ยฑ0.99 / 9.54 ms โ no change โ
โ QQuery 74 โ 586.86 / 590.46 ยฑ3.13 / 596.21 ms โ 583.96 / 654.43 ยฑ42.25 / 692.22 ms โ 1.11x slower โ
โ QQuery 75 โ 276.01 / 278.91 ยฑ1.83 / 281.52 ms โ 284.21 / 287.23 ยฑ2.90 / 292.15 ms โ no change โ
โ QQuery 76 โ 135.73 / 137.29 ยฑ1.15 / 138.47 ms โ 137.05 / 138.25 ยฑ1.17 / 140.27 ms โ no change โ
โ QQuery 77 โ 192.64 / 196.03 ยฑ2.15 / 198.85 ms โ 187.24 / 192.29 ยฑ3.69 / 198.32 ms โ no change โ
โ QQuery 78 โ 355.97 / 364.04 ยฑ4.61 / 369.81 ms โ 336.20 / 348.01 ยฑ9.02 / 360.29 ms โ no change โ
โ QQuery 79 โ 232.58 / 238.11 ยฑ3.46 / 243.02 ms โ 230.76 / 232.73 ยฑ1.46 / 234.65 ms โ no change โ
โ QQuery 80 โ 323.13 / 327.78 ยฑ3.45 / 332.45 ms โ 324.11 / 325.71 ยฑ2.23 / 330.09 ms โ no change โ
โ QQuery 81 โ 25.90 / 27.46 ยฑ1.22 / 29.22 ms โ 25.23 / 26.03 ยฑ0.47 / 26.43 ms โ +1.05x faster โ
โ QQuery 82 โ 40.57 / 41.83 ยฑ1.40 / 44.42 ms โ 40.00 / 40.61 ยฑ0.35 / 40.98 ms โ no change โ
โ QQuery 83 โ 38.41 / 40.52 ยฑ1.98 / 43.66 ms โ 37.92 / 39.03 ยฑ0.95 / 40.51 ms โ no change โ
โ QQuery 84 โ 48.12 / 48.83 ยฑ0.55 / 49.53 ms โ 47.56 / 49.53 ยฑ1.84 / 52.15 ms โ no change โ
โ QQuery 85 โ 145.95 / 147.53 ยฑ1.57 / 150.17 ms โ 146.54 / 148.18 ยฑ1.12 / 149.67 ms โ no change โ
โ QQuery 86 โ 37.28 / 39.18 ยฑ1.11 / 40.59 ms โ 40.55 / 41.33 ยฑ0.62 / 42.42 ms โ 1.05x slower โ
โ QQuery 87 โ 85.75 / 88.07 ยฑ2.62 / 93.17 ms โ 3.60 / 3.80 ยฑ0.19 / 4.09 ms โ +23.19x faster โ
โ QQuery 88 โ 98.00 / 99.06 ยฑ0.62 / 99.89 ms โ 103.22 / 103.76 ยฑ0.37 / 104.30 ms โ no change โ
โ QQuery 89 โ 119.44 / 120.19 ยฑ0.54 / 120.77 ms โ 121.17 / 123.76 ยฑ1.45 / 125.15 ms โ no change โ
โ QQuery 90 โ 23.06 / 23.50 ยฑ0.38 / 24.02 ms โ 24.83 / 25.46 ยฑ0.34 / 25.75 ms โ 1.08x slower โ
โ QQuery 91 โ 61.38 / 63.31 ยฑ1.06 / 64.56 ms โ 66.99 / 68.25 ยฑ0.73 / 69.11 ms โ 1.08x slower โ
โ QQuery 92 โ 56.21 / 57.29 ยฑ1.00 / 59.01 ms โ 60.34 / 61.32 ยฑ0.62 / 62.24 ms โ 1.07x slower โ
โ QQuery 93 โ 184.85 / 186.65 ยฑ1.18 / 188.01 ms โ 198.84 / 200.36 ยฑ0.99 / 201.80 ms โ 1.07x slower โ
โ QQuery 94 โ 62.25 / 62.59 ยฑ0.39 / 63.11 ms โ 65.04 / 67.04 ยฑ1.44 / 69.50 ms โ 1.07x slower โ
โ QQuery 95 โ 129.34 / 129.95 ยฑ0.59 / 130.85 ms โ 135.11 / 136.38 ยฑ1.04 / 138.08 ms โ no change โ
โ QQuery 96 โ 74.15 / 74.77 ยฑ0.57 / 75.69 ms โ 77.42 / 78.52 ยฑ1.00 / 80.14 ms โ 1.05x slower โ
โ QQuery 97 โ 124.80 / 125.61 ยฑ0.56 / 126.20 ms โ 131.70 / 135.68 ยฑ2.28 / 138.06 ms โ 1.08x slower โ
โ QQuery 98 โ 152.95 / 154.34 ยฑ1.04 / 155.76 ms โ 165.03 / 166.91 ยฑ1.38 / 169.11 ms โ 1.08x slower โ
โ QQuery 99 โ 10725.87 / 10871.89 ยฑ78.17 / 10943.25 ms โ 10706.78 / 10824.92 ยฑ80.61 / 10935.60 ms โ no change โ
โโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (HEAD) โ 31753.39ms โ
โ Total Time (use-ndv-for-semi-and-anti-join) โ 31701.36ms โ
โ Average Time (HEAD) โ 320.74ms โ
โ Average Time (use-ndv-for-semi-and-anti-join) โ 320.22ms โ
โ Queries Faster โ 15 โ
โ Queries Slower โ 22 โ
โ Queries with No Change โ 62 โ
โ Queries with Failure โ 0 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpcds โ base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 6.7 GiB |
| Avg memory | 5.6 GiB |
| CPU user | 263.5s |
| CPU sys | 17.1s |
| Peak spill | 0 B |
**tpcds โ branch**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 6.8 GiB |
| Avg memory | 5.6 GiB |
| CPU user | 260.6s |
| CPU sys | 17.1s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286672709
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286657778-1657-pcv4l 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpcds
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286643396
Can we run some benchmarks (e.g. tpch, tpcds, ...) for PRs like these in the future?
Would be good to see impact of individual contributions and possibly catch regressions / issues.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930525523
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,88 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+///
+/// PostgreSQL uses a similar approach in `eqjoinsel_semi`
+/// (`src/backend/utils/adt/selfuncs.c`). When NDV statistics are
+/// available on both sides it computes selectivity as `nd2 / nd1`,
+/// which is equivalent to `min(outer_ndv, inner_ndv) / outer_ndv`.
+/// If either side lacks statistics it falls back to a default.
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+ let inner_rows = *inner_num_rows.get_value()?;
+ if inner_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_selectivity_estimate = false;
+
+ for (outer_stat, inner_stat) in outer_col_stats.iter().zip(inner_col_stats.iter()) {
+ let outer_has_stats = outer_stat.distinct_count.get_value().is_some()
+ || (outer_stat.min_value.get_value().is_some()
+ && outer_stat.max_value.get_value().is_some());
+ let inner_has_stats = inner_stat.distinct_count.get_value().is_some()
+ || (inner_stat.min_value.get_value().is_some()
+ && inner_stat.max_value.get_value().is_some());
+ if !outer_has_stats || !inner_has_stats {
+ continue;
+ }
+
+ let outer_ndv = max_distinct_count(outer_num_rows, outer_stat);
+ let inner_ndv = max_distinct_count(inner_num_rows, inner_stat);
+
+ if let (Some(&o), Some(&i)) = (outer_ndv.get_value(), inner_ndv.get_value())
+ && o > 0
+ {
+ selectivity *= (o.min(i) as f64) / (o as f64);
Review Comment:
I took a look at the Postgres' implementation (the branch without the "most common values", which we don't track), I noticed a potential improvement over what we have now.
Postgres uses `selec = min(1, inner_ndv/outer_ndv) * (1 - nullfrac)` as core formula ([code is here](https://github.com/postgres/postgres/blob/f30cebb9542358702ca0f2c4be2cd504a2568606/src/backend/utils/adt/selfuncs.c#L2872): I have "condensed" the if/else into a single formula and renamed the variables `ndv1 -> outer_ndv` and `ndv2 -> inner_ndv`, so it's clear, but it's equivalent to the code).
We use `selec = min(inner_ndv, outer_ndv) / outer_ndv` (renamed again for readability here), which is equivalent to Postgres' `min(1, inner_ndv/outer_ndv)`.
We don't account for `NULL` values, we are missing the `* (1 - nullfrac)` part of their formula.
Postgres removes them, as `NULL` values cannot ever match, and we could do that too, when `ColumnStatistics::null_count` is available.
We could do it this way:
```suggestion
let null_frac = outer_stat.null_count
.get_value()
.map(|&nc| nc as f64 / outer_rows as f64)
.unwrap_or(0.0);
selectivity *= (o.min(i) as f64) / (o as f64) * (1.0 - null_frac);
```
WDYT?
If you accept the change, we would need a few additional test cases to exercise this part of the code, I can think of these cases:
- single column with nulls on outer side
- anti-join with nulls
- all outer rows are null
- multi-column with nulls on one column
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2925081745
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_ndv = false;
Review Comment:
Nit: this is more about having a selectivity estimate than NDV (judging on lines 774 which set it, and 778 that consumes it), how would `has_selectivity_estimate` sound?
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -2634,6 +2719,49 @@ mod tests {
(10, Inexact(30), Absent, Absent, Absent),
Some(50),
),
+ // NDV-based semi join: outer_ndv=20, inner_ndv=10
Review Comment:
Good test coverage, but I'd also add test cases for:
- Multi-column join keys (to exercise the multiplicative selectivity path, which is new code)
- Mixed stats availability (one column has NDV, another doesn't)
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
Review Comment:
The math looks sound to me, and coherent with that of https://github.com/apache/datafusion/pull/20846.
I was wondering if you did check other notable systems using CBO like Trino or Spark.
If so, consider adding a note, this will help reviewers trust the change, as already battle-tested elsewhere.
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_ndv = false;
+
+ for (outer_stat, inner_stat) in outer_col_stats.iter().zip(inner_col_stats.iter()) {
+ let outer_has_stats = outer_stat.distinct_count.get_value().is_some()
+ || (outer_stat.min_value.get_value().is_some()
+ && outer_stat.max_value.get_value().is_some());
+ let inner_has_stats = inner_stat.distinct_count.get_value().is_some()
+ || (inner_stat.min_value.get_value().is_some()
+ && inner_stat.max_value.get_value().is_some());
+ if !outer_has_stats && !inner_has_stats {
Review Comment:
I'd rather be even more conservative, and turn the AND into an OR: with missing stats (both NDV and min/max), the number of rows is used as fallback, mixing it NDV would make the estimation probably too inaccurate to be useful, so my suggestion is as-follows:
```suggestion
if !outer_has_stats || !inner_has_stats {
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2927660654
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
Review Comment:
Yes I think we can look into what trino did, I think they had something for this, but the postgres approach makes sense
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286668352
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286657778-1656-zzhxn 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: clickbench_partitioned
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286822404
`โ QQuery 87 โ 85.75 / 88.07 ยฑ2.62 / 93.17 ms โ 3.60 / 3.80 ยฑ0.19 / 4.09 ms โ +23.19x faster โ`
Interesting!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286681578
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286664748)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286664748-1660-jltq5 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpch
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286868186
๐ค Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286764315)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and use-ndv-for-semi-and-anti-join
--------------------
Benchmark tpcds_sf1.json
--------------------
โโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโ
โ Query โ HEAD โ use-ndv-for-semi-and-anti-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 6.50 / 6.93 ยฑ0.72 / 8.37 ms โ 6.50 / 6.88 ยฑ0.70 / 8.29 ms โ no change โ
โ QQuery 2 โ 147.80 / 148.79 ยฑ0.72 / 149.98 ms โ 145.90 / 147.29 ยฑ1.00 / 148.59 ms โ no change โ
โ QQuery 3 โ 114.64 / 115.80 ยฑ1.18 / 118.00 ms โ 113.74 / 114.29 ยฑ0.52 / 115.13 ms โ no change โ
โ QQuery 4 โ 1309.33 / 1330.70 ยฑ12.99 / 1347.24 ms โ 1296.30 / 1322.23 ยฑ17.58 / 1345.81 ms โ no change โ
โ QQuery 5 โ 173.18 / 173.93 ยฑ0.41 / 174.31 ms โ 173.98 / 175.64 ยฑ1.46 / 177.94 ms โ no change โ
โ QQuery 6 โ 827.65 / 851.71 ยฑ21.91 / 885.61 ms โ 845.56 / 866.91 ยฑ17.66 / 887.56 ms โ no change โ
โ QQuery 7 โ 340.37 / 344.31 ยฑ2.22 / 346.95 ms โ 339.07 / 343.20 ยฑ3.84 / 350.04 ms โ no change โ
โ QQuery 8 โ 116.01 / 117.89 ยฑ1.15 / 119.26 ms โ 114.14 / 116.70 ยฑ1.49 / 118.35 ms โ no change โ
โ QQuery 9 โ 101.97 / 107.00 ยฑ4.74 / 114.97 ms โ 102.87 / 105.69 ยฑ1.44 / 106.82 ms โ no change โ
โ QQuery 10 โ 105.45 / 106.43 ยฑ0.72 / 107.24 ms โ 104.56 / 105.86 ยฑ1.04 / 107.15 ms โ no change โ
โ QQuery 11 โ 930.44 / 943.03 ยฑ7.99 / 954.30 ms โ 929.20 / 943.86 ยฑ11.12 / 955.59 ms โ no change โ
โ QQuery 12 โ 44.83 / 45.61 ยฑ0.58 / 46.26 ms โ 44.43 / 46.20 ยฑ1.37 / 48.20 ms โ no change โ
โ QQuery 13 โ 396.18 / 400.46 ยฑ2.60 / 403.51 ms โ 402.21 / 405.79 ยฑ2.24 / 409.11 ms โ no change โ
โ QQuery 14 โ 1008.21 / 1016.16 ยฑ7.94 / 1030.03 ms โ 1006.52 / 1009.43 ยฑ3.33 / 1015.62 ms โ no change โ
โ QQuery 15 โ 15.52 / 16.53 ยฑ1.23 / 18.94 ms โ 15.22 / 15.93 ยฑ0.69 / 17.20 ms โ no change โ
โ QQuery 16 โ 7.33 / 8.22 ยฑ0.94 / 9.71 ms โ 7.25 / 8.12 ยฑ0.89 / 9.35 ms โ no change โ
โ QQuery 17 โ 230.28 / 230.39 ยฑ0.10 / 230.52 ms โ 228.54 / 231.89 ยฑ1.75 / 233.43 ms โ no change โ
โ QQuery 18 โ 127.04 / 128.06 ยฑ1.09 / 130.04 ms โ 127.05 / 128.72 ยฑ1.31 / 130.45 ms โ no change โ
โ QQuery 19 โ 154.48 / 155.70 ยฑ0.99 / 156.82 ms โ 155.05 / 157.13 ยฑ1.26 / 158.91 ms โ no change โ
โ QQuery 20 โ 13.23 / 14.04 ยฑ0.70 / 15.05 ms โ 13.51 / 14.22 ยฑ0.56 / 15.06 ms โ no change โ
โ QQuery 21 โ 19.31 / 19.71 ยฑ0.25 / 20.01 ms โ 18.92 / 19.80 ยฑ0.59 / 20.62 ms โ no change โ
โ QQuery 22 โ 484.33 / 487.03 ยฑ1.86 / 489.23 ms โ 483.55 / 486.45 ยฑ2.75 / 491.19 ms โ no change โ
โ QQuery 23 โ 871.93 / 881.92 ยฑ7.27 / 892.37 ms โ 861.04 / 872.89 ยฑ8.74 / 885.04 ms โ no change โ
โ QQuery 24 โ 381.29 / 384.84 ยฑ2.51 / 388.11 ms โ 381.28 / 382.82 ยฑ1.90 / 386.40 ms โ no change โ
โ QQuery 25 โ 341.44 / 342.93 ยฑ1.11 / 344.51 ms โ 338.52 / 341.34 ยฑ2.16 / 344.45 ms โ no change โ
โ QQuery 26 โ 81.55 / 82.83 ยฑ1.45 / 84.85 ms โ 80.75 / 82.27 ยฑ0.86 / 83.30 ms โ no change โ
โ QQuery 27 โ 6.75 / 7.44 ยฑ0.61 / 8.25 ms โ 6.86 / 7.30 ยฑ0.33 / 7.83 ms โ no change โ
โ QQuery 28 โ 149.28 / 150.16 ยฑ0.89 / 151.54 ms โ 149.81 / 151.51 ยฑ1.31 / 153.86 ms โ no change โ
โ QQuery 29 โ 280.30 / 281.92 ยฑ1.82 / 285.20 ms โ 280.01 / 282.04 ยฑ1.83 / 285.22 ms โ no change โ
โ QQuery 30 โ 43.40 / 45.76 ยฑ1.35 / 47.56 ms โ 43.04 / 46.04 ยฑ1.61 / 47.59 ms โ no change โ
โ QQuery 31 โ 169.93 / 171.64 ยฑ1.01 / 172.55 ms โ 171.87 / 173.18 ยฑ1.53 / 176.15 ms โ no change โ
โ QQuery 32 โ 13.85 / 14.77 ยฑ1.08 / 16.77 ms โ 13.48 / 13.83 ยฑ0.20 / 14.08 ms โ +1.07x faster โ
โ QQuery 33 โ 139.11 / 142.24 ยฑ1.95 / 145.05 ms โ 138.87 / 141.48 ยฑ1.80 / 143.82 ms โ no change โ
โ QQuery 34 โ 7.03 / 7.43 ยฑ0.45 / 8.26 ms โ 6.82 / 7.10 ยฑ0.24 / 7.51 ms โ no change โ
โ QQuery 35 โ 108.43 / 109.93 ยฑ1.27 / 111.79 ms โ 103.08 / 108.13 ยฑ2.62 / 110.55 ms โ no change โ
โ QQuery 36 โ 6.79 / 7.32 ยฑ0.80 / 8.91 ms โ 6.39 / 6.92 ยฑ0.50 / 7.86 ms โ +1.06x faster โ
โ QQuery 37 โ 8.34 / 8.78 ยฑ0.39 / 9.31 ms โ 8.70 / 9.25 ยฑ0.64 / 10.49 ms โ 1.05x slower โ
โ QQuery 38 โ 84.39 / 89.84 ยฑ4.76 / 96.78 ms โ 93.69 / 97.43 ยฑ2.14 / 99.90 ms โ 1.08x slower โ
โ QQuery 39 โ 125.05 / 129.19 ยฑ2.53 / 132.53 ms โ 123.39 / 127.13 ยฑ2.09 / 129.45 ms โ no change โ
โ QQuery 40 โ 114.18 / 117.69 ยฑ5.40 / 128.36 ms โ 108.82 / 114.30 ยฑ6.68 / 126.21 ms โ no change โ
โ QQuery 41 โ 14.31 / 14.97 ยฑ0.33 / 15.20 ms โ 14.01 / 15.00 ยฑ0.71 / 16.14 ms โ no change โ
โ QQuery 42 โ 108.44 / 109.73 ยฑ1.07 / 110.97 ms โ 107.07 / 109.18 ยฑ1.48 / 111.11 ms โ no change โ
โ QQuery 43 โ 5.57 / 5.73 ยฑ0.18 / 6.08 ms โ 5.60 / 5.79 ยฑ0.16 / 6.03 ms โ no change โ
โ QQuery 44 โ 11.80 / 11.95 ยฑ0.19 / 12.32 ms โ 11.56 / 11.98 ยฑ0.37 / 12.44 ms โ no change โ
โ QQuery 45 โ 51.75 / 52.29 ยฑ0.81 / 53.90 ms โ 51.11 / 51.42 ยฑ0.38 / 52.17 ms โ no change โ
โ QQuery 46 โ 8.29 / 8.53 ยฑ0.25 / 8.96 ms โ 8.16 / 8.48 ยฑ0.21 / 8.80 ms โ no change โ
โ QQuery 47 โ 720.53 / 727.27 ยฑ3.99 / 731.64 ms โ 707.26 / 717.71 ยฑ5.98 / 724.63 ms โ no change โ
โ QQuery 48 โ 288.90 / 296.87 ยฑ4.51 / 301.23 ms โ 285.94 / 291.99 ยฑ4.90 / 296.83 ms โ no change โ
โ QQuery 49 โ 254.16 / 258.22 ยฑ2.87 / 262.48 ms โ 253.03 / 255.36 ยฑ1.78 / 257.94 ms โ no change โ
โ QQuery 50 โ 226.95 / 230.73 ยฑ2.92 / 234.47 ms โ 213.17 / 223.62 ยฑ7.11 / 233.07 ms โ no change โ
โ QQuery 51 โ 179.47 / 184.37 ยฑ3.14 / 189.20 ms โ 180.79 / 182.36 ยฑ1.65 / 185.27 ms โ no change โ
โ QQuery 52 โ 107.85 / 108.61 ยฑ0.85 / 110.25 ms โ 107.59 / 108.58 ยฑ0.67 / 109.62 ms โ no change โ
โ QQuery 53 โ 103.08 / 104.97 ยฑ1.50 / 106.65 ms โ 102.44 / 104.44 ยฑ1.62 / 106.40 ms โ no change โ
โ QQuery 54 โ 146.42 / 147.50 ยฑ1.03 / 149.35 ms โ 143.55 / 146.46 ยฑ1.59 / 148.37 ms โ no change โ
โ QQuery 55 โ 107.25 / 107.92 ยฑ0.88 / 109.65 ms โ 106.99 / 108.64 ยฑ1.33 / 110.32 ms โ no change โ
โ QQuery 56 โ 140.60 / 142.68 ยฑ1.53 / 144.36 ms โ 141.34 / 142.84 ยฑ1.25 / 144.62 ms โ no change โ
โ QQuery 57 โ 170.93 / 174.74 ยฑ2.89 / 177.28 ms โ 171.09 / 173.89 ยฑ1.54 / 175.14 ms โ no change โ
โ QQuery 58 โ 274.48 / 275.85 ยฑ0.73 / 276.57 ms โ 318.23 / 320.04 ยฑ1.39 / 321.84 ms โ 1.16x slower โ
โ QQuery 59 โ 199.15 / 199.93 ยฑ0.91 / 201.57 ms โ 196.75 / 198.63 ยฑ1.00 / 199.40 ms โ no change โ
โ QQuery 60 โ 142.53 / 145.07 ยฑ2.13 / 148.08 ms โ 142.20 / 143.94 ยฑ1.67 / 146.64 ms โ no change โ
โ QQuery 61 โ 13.06 / 13.22 ยฑ0.09 / 13.34 ms โ 12.70 / 12.91 ยฑ0.28 / 13.45 ms โ no change โ
โ QQuery 62 โ 883.24 / 920.83 ยฑ24.13 / 948.13 ms โ 877.61 / 933.48 ยฑ40.77 / 989.54 ms โ no change โ
โ QQuery 63 โ 104.85 / 108.45 ยฑ2.56 / 111.33 ms โ 105.01 / 107.69 ยฑ1.98 / 110.08 ms โ no change โ
โ QQuery 64 โ 685.34 / 690.86 ยฑ4.84 / 697.70 ms โ 683.99 / 689.11 ยฑ4.08 / 696.22 ms โ no change โ
โ QQuery 65 โ 250.62 / 254.71 ยฑ3.26 / 260.42 ms โ 248.16 / 250.93 ยฑ2.43 / 254.53 ms โ no change โ
โ QQuery 66 โ 250.46 / 255.59 ยฑ3.16 / 259.69 ms โ 237.07 / 250.19 ยฑ11.39 / 265.08 ms โ no change โ
โ QQuery 67 โ 310.59 / 316.52 ยฑ4.86 / 323.93 ms โ 304.83 / 315.90 ยฑ11.03 / 336.78 ms โ no change โ
โ QQuery 68 โ 8.36 / 9.05 ยฑ0.74 / 10.48 ms โ 8.62 / 10.86 ยฑ1.52 / 12.58 ms โ 1.20x slower โ
โ QQuery 69 โ 102.21 / 103.49 ยฑ1.25 / 105.04 ms โ 101.55 / 103.58 ยฑ1.29 / 105.47 ms โ no change โ
โ QQuery 70 โ 334.60 / 347.02 ยฑ12.14 / 370.30 ms โ 331.40 / 350.51 ยฑ13.42 / 373.15 ms โ no change โ
โ QQuery 71 โ 135.31 / 137.17 ยฑ1.65 / 139.25 ms โ 135.48 / 137.10 ยฑ1.68 / 140.30 ms โ no change โ
โ QQuery 72 โ 615.01 / 619.88 ยฑ5.32 / 629.37 ms โ 614.82 / 627.97 ยฑ10.29 / 644.25 ms โ no change โ
โ QQuery 73 โ 6.70 / 7.75 ยฑ0.85 / 8.90 ms โ 6.55 / 8.02 ยฑ1.22 / 10.23 ms โ no change โ
โ QQuery 74 โ 584.37 / 593.13 ยฑ6.95 / 601.45 ms โ 563.40 / 573.94 ยฑ6.44 / 581.98 ms โ no change โ
โ QQuery 75 โ 273.01 / 277.45 ยฑ2.87 / 281.43 ms โ 275.58 / 278.67 ยฑ2.50 / 281.48 ms โ no change โ
โ QQuery 76 โ 131.80 / 133.42 ยฑ0.97 / 134.50 ms โ 131.12 / 133.31 ยฑ2.13 / 136.05 ms โ no change โ
โ QQuery 77 โ 189.32 / 190.42 ยฑ1.35 / 193.06 ms โ 187.48 / 189.90 ยฑ2.36 / 194.21 ms โ no change โ
โ QQuery 78 โ 341.40 / 344.94 ยฑ3.24 / 349.15 ms โ 337.74 / 342.76 ยฑ3.22 / 346.79 ms โ no change โ
โ QQuery 79 โ 231.49 / 235.69 ยฑ3.39 / 241.77 ms โ 230.20 / 234.24 ยฑ3.23 / 238.14 ms โ no change โ
โ QQuery 80 โ 323.06 / 327.51 ยฑ2.75 / 330.97 ms โ 323.85 / 326.29 ยฑ3.05 / 332.13 ms โ no change โ
โ QQuery 81 โ 25.79 / 27.15 ยฑ1.19 / 28.89 ms โ 26.14 / 26.82 ยฑ0.68 / 28.01 ms โ no change โ
โ QQuery 82 โ 39.71 / 41.33 ยฑ1.20 / 43.08 ms โ 41.14 / 41.49 ยฑ0.35 / 42.11 ms โ no change โ
โ QQuery 83 โ 38.53 / 39.12 ยฑ0.46 / 39.94 ms โ 37.89 / 39.54 ยฑ1.65 / 42.60 ms โ no change โ
โ QQuery 84 โ 48.13 / 49.02 ยฑ1.05 / 50.91 ms โ 48.30 / 49.86 ยฑ1.34 / 52.34 ms โ no change โ
โ QQuery 85 โ 147.75 / 149.25 ยฑ1.12 / 150.75 ms โ 147.33 / 149.64 ยฑ2.58 / 154.62 ms โ no change โ
โ QQuery 86 โ 38.36 / 39.64 ยฑ0.80 / 40.65 ms โ 38.61 / 39.14 ยฑ0.34 / 39.51 ms โ no change โ
โ QQuery 87 โ 86.85 / 89.70 ยฑ3.00 / 95.07 ms โ 3.36 / 3.48 ยฑ0.19 / 3.87 ms โ +25.77x faster โ
โ QQuery 88 โ 99.89 / 101.01 ยฑ1.40 / 103.55 ms โ 98.34 / 99.05 ยฑ0.42 / 99.64 ms โ no change โ
โ QQuery 89 โ 120.01 / 121.03 ยฑ0.84 / 122.41 ms โ 117.76 / 119.00 ยฑ1.13 / 121.01 ms โ no change โ
โ QQuery 90 โ 23.86 / 24.34 ยฑ0.50 / 25.29 ms โ 22.75 / 23.44 ยฑ0.37 / 23.83 ms โ no change โ
โ QQuery 91 โ 62.53 / 65.14 ยฑ2.30 / 69.26 ms โ 62.19 / 64.26 ยฑ2.23 / 67.90 ms โ no change โ
โ QQuery 92 โ 58.08 / 58.90 ยฑ0.57 / 59.67 ms โ 57.37 / 58.19 ยฑ0.70 / 59.24 ms โ no change โ
โ QQuery 93 โ 185.33 / 188.45 ยฑ1.76 / 189.98 ms โ 185.93 / 188.09 ยฑ1.43 / 189.80 ms โ no change โ
โ QQuery 94 โ 62.90 / 63.34 ยฑ0.37 / 63.86 ms โ 62.30 / 63.62 ยฑ0.99 / 64.90 ms โ no change โ
โ QQuery 95 โ 131.50 / 133.31 ยฑ1.40 / 134.53 ms โ 130.26 / 131.68 ยฑ1.20 / 133.51 ms โ no change โ
โ QQuery 96 โ 71.67 / 74.31 ยฑ1.40 / 75.74 ms โ 72.93 / 73.58 ยฑ0.80 / 74.96 ms โ no change โ
โ QQuery 97 โ 126.24 / 128.50 ยฑ2.02 / 131.78 ms โ 125.38 / 128.41 ยฑ1.96 / 130.93 ms โ no change โ
โ QQuery 98 โ 153.05 / 154.07 ยฑ0.58 / 154.65 ms โ 150.15 / 153.68 ยฑ2.56 / 157.40 ms โ no change โ
โ QQuery 99 โ 10742.43 / 10782.57 ยฑ34.38 / 10834.75 ms โ 10731.90 / 10754.02 ยฑ16.29 / 10777.09 ms โ no change โ
โโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (HEAD) โ 31270.23ms โ
โ Total Time (use-ndv-for-semi-and-anti-join) โ 31141.86ms โ
โ Average Time (HEAD) โ 315.86ms โ
โ Average Time (use-ndv-for-semi-and-anti-join) โ 314.56ms โ
โ Queries Faster โ 3 โ
โ Queries Slower โ 4 โ
โ Queries with No Change โ 92 โ
โ Queries with Failure โ 0 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**tpcds โ base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 6.7 GiB |
| Avg memory | 5.6 GiB |
| CPU user | 259.9s |
| CPU sys | 16.7s |
| Peak spill | 0 B |
**tpcds โ branch**
| Metric | Value |
|--------|-------|
| Wall time | 160.0s |
| Peak memory | 6.6 GiB |
| Avg memory | 5.5 GiB |
| CPU user | 256.7s |
| CPU sys | 16.8s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2925310392
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,78 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
Review Comment:
This builds up on same assumption in the inner join in the same file `estimate_inner_join_cardinality`. I saw similar thing in postgres https://github.com/postgres/postgres/blob/02976b0a1718037f73fded250411b013e81fdafa/src/backend/utils/adt/selfuncs.c#L2718. I may need to check Spark and Trino again. In the epic it said about them but not sure about this.
If you have any reservations about I can close or maybe try to be more conservative on this
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930632531
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,88 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+///
+/// PostgreSQL uses a similar approach in `eqjoinsel_semi`
+/// (`src/backend/utils/adt/selfuncs.c`). When NDV statistics are
+/// available on both sides it computes selectivity as `nd2 / nd1`,
+/// which is equivalent to `min(outer_ndv, inner_ndv) / outer_ndv`.
+/// If either side lacks statistics it falls back to a default.
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+ let inner_rows = *inner_num_rows.get_value()?;
+ if inner_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_selectivity_estimate = false;
+
+ for (outer_stat, inner_stat) in outer_col_stats.iter().zip(inner_col_stats.iter()) {
+ let outer_has_stats = outer_stat.distinct_count.get_value().is_some()
+ || (outer_stat.min_value.get_value().is_some()
+ && outer_stat.max_value.get_value().is_some());
+ let inner_has_stats = inner_stat.distinct_count.get_value().is_some()
+ || (inner_stat.min_value.get_value().is_some()
+ && inner_stat.max_value.get_value().is_some());
+ if !outer_has_stats || !inner_has_stats {
+ continue;
+ }
+
+ let outer_ndv = max_distinct_count(outer_num_rows, outer_stat);
+ let inner_ndv = max_distinct_count(inner_num_rows, inner_stat);
+
+ if let (Some(&o), Some(&i)) = (outer_ndv.get_value(), inner_ndv.get_value())
+ && o > 0
+ {
+ selectivity *= (o.min(i) as f64) / (o as f64);
Review Comment:
Thanks @asolimando I've added your part and will add test cases now
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286798209
๐ค Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and use-ndv-for-semi-and-anti-join
--------------------
Benchmark clickbench_partitioned.json
--------------------
โโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโโโโ
โ Query โ HEAD โ use-ndv-for-semi-and-anti-join โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 0 โ 1.16 / 4.39 ยฑ6.33 / 17.05 ms โ 1.17 / 4.35 ยฑ6.27 / 16.90 ms โ no change โ
โ QQuery 1 โ 12.42 / 13.01 ยฑ0.36 / 13.52 ms โ 12.35 / 12.88 ยฑ0.30 / 13.28 ms โ no change โ
โ QQuery 2 โ 36.92 / 37.06 ยฑ0.20 / 37.46 ms โ 36.45 / 36.58 ยฑ0.12 / 36.75 ms โ no change โ
โ QQuery 3 โ 31.19 / 31.97 ยฑ0.81 / 33.47 ms โ 31.50 / 31.66 ยฑ0.14 / 31.88 ms โ no change โ
โ QQuery 4 โ 253.24 / 255.57 ยฑ2.48 / 259.20 ms โ 247.31 / 260.80 ยฑ8.16 / 272.66 ms โ no change โ
โ QQuery 5 โ 294.44 / 297.06 ยฑ2.11 / 299.49 ms โ 293.68 / 302.22 ยฑ5.36 / 310.44 ms โ no change โ
โ QQuery 6 โ 5.62 / 7.17 ยฑ1.17 / 8.98 ms โ 6.29 / 7.32 ยฑ0.60 / 8.17 ms โ no change โ
โ QQuery 7 โ 14.46 / 14.69 ยฑ0.13 / 14.86 ms โ 13.63 / 13.95 ยฑ0.35 / 14.61 ms โ +1.05x faster โ
โ QQuery 8 โ 362.09 / 369.96 ยฑ6.49 / 378.06 ms โ 368.28 / 372.45 ยฑ4.79 / 380.07 ms โ no change โ
โ QQuery 9 โ 532.66 / 538.56 ยฑ5.16 / 546.06 ms โ 511.32 / 520.28 ยฑ8.85 / 536.40 ms โ no change โ
โ QQuery 10 โ 76.20 / 77.74 ยฑ1.84 / 81.00 ms โ 74.38 / 76.88 ยฑ2.24 / 81.08 ms โ no change โ
โ QQuery 11 โ 85.67 / 86.13 ยฑ0.36 / 86.61 ms โ 85.57 / 85.88 ยฑ0.36 / 86.53 ms โ no change โ
โ QQuery 12 โ 291.12 / 298.04 ยฑ4.58 / 303.68 ms โ 294.57 / 308.24 ยฑ10.77 / 326.16 ms โ no change โ
โ QQuery 13 โ 425.30 / 450.48 ยฑ30.14 / 507.68 ms โ 424.82 / 443.19 ยฑ19.72 / 475.27 ms โ no change โ
โ QQuery 14 โ 305.45 / 310.84 ยฑ5.25 / 320.60 ms โ 309.30 / 312.95 ยฑ2.59 / 316.51 ms โ no change โ
โ QQuery 15 โ 322.75 / 332.62 ยฑ7.53 / 345.19 ms โ 328.94 / 347.13 ยฑ19.35 / 384.27 ms โ no change โ
โ QQuery 16 โ 686.53 / 707.14 ยฑ16.50 / 726.29 ms โ 683.33 / 689.75 ยฑ5.43 / 699.17 ms โ no change โ
โ QQuery 17 โ 678.14 / 684.44 ยฑ4.80 / 691.75 ms โ 681.96 / 691.09 ยฑ6.14 / 700.38 ms โ no change โ
โ QQuery 18 โ 1429.11 / 1481.99 ยฑ42.96 / 1556.50 ms โ 1350.51 / 1366.00 ยฑ19.79 / 1403.41 ms โ +1.08x faster โ
โ QQuery 19 โ 30.45 / 35.12 ยฑ8.91 / 52.94 ms โ 30.59 / 31.61 ยฑ1.05 / 33.26 ms โ +1.11x faster โ
โ QQuery 20 โ 518.45 / 531.27 ยฑ12.94 / 548.44 ms โ 512.68 / 518.49 ยฑ6.08 / 529.71 ms โ no change โ
โ QQuery 21 โ 592.25 / 600.87 ยฑ8.70 / 616.07 ms โ 595.75 / 598.07 ยฑ1.55 / 599.98 ms โ no change โ
โ QQuery 22 โ 1055.13 / 1062.36 ยฑ4.71 / 1067.62 ms โ 1055.87 / 1057.49 ยฑ1.33 / 1059.37 ms โ no change โ
โ QQuery 23 โ 3291.59 / 3315.49 ยฑ23.15 / 3357.33 ms โ 3282.80 / 3294.55 ยฑ8.26 / 3303.69 ms โ no change โ
โ QQuery 24 โ 45.77 / 47.69 ยฑ2.77 / 53.16 ms โ 43.38 / 45.27 ยฑ2.20 / 49.39 ms โ +1.05x faster โ
โ QQuery 25 โ 115.21 / 116.55 ยฑ1.14 / 117.93 ms โ 116.11 / 117.36 ยฑ0.64 / 117.91 ms โ no change โ
โ QQuery 26 โ 42.96 / 44.38 ยฑ1.15 / 46.37 ms โ 42.50 / 43.39 ยฑ0.62 / 44.01 ms โ no change โ
โ QQuery 27 โ 663.10 / 667.60 ยฑ4.25 / 675.70 ms โ 665.76 / 670.11 ยฑ5.11 / 679.14 ms โ no change โ
โ QQuery 28 โ 2979.09 / 3023.24 ยฑ30.17 / 3072.57 ms โ 2975.67 / 3021.18 ยฑ24.62 / 3050.60 ms โ no change โ
โ QQuery 29 โ 44.36 / 47.96 ยฑ3.00 / 52.56 ms โ 43.89 / 48.66 ยฑ3.92 / 55.01 ms โ no change โ
โ QQuery 30 โ 327.66 / 332.63 ยฑ5.01 / 341.76 ms โ 331.13 / 336.39 ยฑ6.13 / 347.70 ms โ no change โ
โ QQuery 31 โ 337.39 / 345.20 ยฑ5.45 / 354.18 ms โ 326.73 / 330.91 ยฑ6.02 / 342.59 ms โ no change โ
โ QQuery 32 โ 1156.76 / 1239.36 ยฑ52.89 / 1322.58 ms โ 1018.91 / 1027.33 ยฑ6.66 / 1038.90 ms โ +1.21x faster โ
โ QQuery 33 โ 1478.22 / 1509.01 ยฑ31.72 / 1560.59 ms โ 1437.45 / 1463.57 ยฑ25.85 / 1497.89 ms โ no change โ
โ QQuery 34 โ 1498.76 / 1594.43 ยฑ65.90 / 1678.40 ms โ 1469.84 / 1486.05 ยฑ19.68 / 1524.64 ms โ +1.07x faster โ
โ QQuery 35 โ 321.71 / 327.91 ยฑ6.85 / 341.08 ms โ 320.46 / 325.82 ยฑ6.52 / 338.19 ms โ no change โ
โ QQuery 36 โ 61.59 / 65.13 ยฑ3.26 / 70.84 ms โ 62.44 / 67.38 ยฑ2.82 / 70.42 ms โ no change โ
โ QQuery 37 โ 37.47 / 39.20 ยฑ1.18 / 40.54 ms โ 37.45 / 39.22 ยฑ1.30 / 41.44 ms โ no change โ
โ QQuery 38 โ 41.04 / 42.41 ยฑ0.93 / 43.61 ms โ 40.30 / 42.37 ยฑ1.43 / 44.12 ms โ no change โ
โ QQuery 39 โ 125.53 / 130.77 ยฑ5.20 / 139.78 ms โ 119.41 / 128.71 ยฑ5.86 / 137.25 ms โ no change โ
โ QQuery 40 โ 14.61 / 17.44 ยฑ2.33 / 19.90 ms โ 14.76 / 16.33 ยฑ1.40 / 18.35 ms โ +1.07x faster โ
โ QQuery 41 โ 15.19 / 16.12 ยฑ1.11 / 18.16 ms โ 13.59 / 14.80 ยฑ1.25 / 16.86 ms โ +1.09x faster โ
โ QQuery 42 โ 13.62 / 14.11 ยฑ0.38 / 14.75 ms โ 13.33 / 14.54 ยฑ1.08 / 16.02 ms โ no change โ
โโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (HEAD) โ 21165.10ms โ
โ Total Time (use-ndv-for-semi-and-anti-join) โ 20623.20ms โ
โ Average Time (HEAD) โ 492.21ms โ
โ Average Time (use-ndv-for-semi-and-anti-join) โ 479.61ms โ
โ Queries Faster โ 8 โ
โ Queries Slower โ 0 โ
โ Queries with No Change โ 35 โ
โ Queries with Failure โ 0 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโ
```
</p>
</details>
<details><summary>Resource Usage</summary>
**clickbench_partitioned โ base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 110.0s |
| Peak memory | 34.9 GiB |
| Avg memory | 27.1 GiB |
| CPU user | 1082.5s |
| CPU sys | 103.6s |
| Peak spill | 0 B |
**clickbench_partitioned โ branch**
| Metric | Value |
|--------|-------|
| Wall time | 105.0s |
| Peak memory | 39.4 GiB |
| Avg memory | 33.5 GiB |
| CPU user | 1079.5s |
| CPU sys | 84.3s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4287415268
Benchmark for [this request](https://github.com/apache/datafusion/pull/20904#issuecomment-4286664748) hit the 7200s job deadline before finishing.
Benchmarks requested: `tpch`
<details><summary>Kubernetes message</summary>
```
Job was active longer than specified deadline
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286658978
> Can we run some benchmarks (e.g. tpch, tpcds, ...) for PRs like these in the future?
>
> Would be good to see impact of individual contributions and possibly catch regressions / issues.
Sure, running
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286780190
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286764315)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286764315-1667-vb9vk 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpcds
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4287406913
Benchmark for [this request](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778) hit the 7200s job deadline before finishing.
Benchmarks requested: `tpch`
<details><summary>Kubernetes message</summary>
```
Job was active longer than specified deadline
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286905802
> `โ QQuery 87 โ 85.75 / 88.07 ยฑ2.62 / 93.17 ms โ 3.60 / 3.80 ยฑ0.19 / 4.09 ms โ +23.19x faster โ`
>
> Interesting!
The magic of stats!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2925194755
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -2634,6 +2719,49 @@ mod tests {
(10, Inexact(30), Absent, Absent, Absent),
Some(50),
),
+ // NDV-based semi join: outer_ndv=20, inner_ndv=10
Review Comment:
Of course let me add it
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#discussion_r2930682341
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -697,6 +710,88 @@ fn estimate_disjoint_inputs(
None
}
+/// Estimates the number of outer rows that have at least one matching
+/// key on the inner side (i.e. semi join cardinality) using NDV
+/// (Number of Distinct Values) statistics.
+///
+/// Assuming the smaller domain is contained in the larger, the number
+/// of overlapping distinct values is `min(outer_ndv, inner_ndv)`.
+/// Under the uniformity assumption (each distinct value contributes
+/// equally to row counts), the surviving fraction of outer rows is:
+///
+/// ```text
+/// overlap_fraction = min(outer_ndv, inner_ndv) / outer_ndv
+/// ```
+///
+/// For multi-column join keys, each column pair contributes an
+/// independent selectivity factor and the overall selectivity is the
+/// product of these factors:
+///
+/// ```text
+/// selectivity = product_i(min(outer_ndv_i, inner_ndv_i) / outer_ndv_i)
+/// semi_cardinality = outer_rows * selectivity
+/// ```
+///
+/// Anti join cardinality is derived as the complement:
+/// `outer_rows - semi_cardinality`.
+///
+/// Boundary cases:
+/// * `inner_ndv >= outer_ndv` โ selectivity = 1.0 (all outer rows match)
+/// * `inner_ndv = 0` โ selectivity = 0.0
+/// * Missing NDV statistics โ returns `None` (fallback to `outer_rows`)
+///
+/// PostgreSQL uses a similar approach in `eqjoinsel_semi`
+/// (`src/backend/utils/adt/selfuncs.c`). When NDV statistics are
+/// available on both sides it computes selectivity as `nd2 / nd1`,
+/// which is equivalent to `min(outer_ndv, inner_ndv) / outer_ndv`.
+/// If either side lacks statistics it falls back to a default.
+fn estimate_semi_join_cardinality(
+ outer_num_rows: &Precision<usize>,
+ inner_num_rows: &Precision<usize>,
+ outer_col_stats: &[ColumnStatistics],
+ inner_col_stats: &[ColumnStatistics],
+) -> Option<usize> {
+ let outer_rows = *outer_num_rows.get_value()?;
+ if outer_rows == 0 {
+ return Some(0);
+ }
+ let inner_rows = *inner_num_rows.get_value()?;
+ if inner_rows == 0 {
+ return Some(0);
+ }
+
+ let mut selectivity = 1.0_f64;
+ let mut has_selectivity_estimate = false;
+
+ for (outer_stat, inner_stat) in outer_col_stats.iter().zip(inner_col_stats.iter()) {
+ let outer_has_stats = outer_stat.distinct_count.get_value().is_some()
+ || (outer_stat.min_value.get_value().is_some()
+ && outer_stat.max_value.get_value().is_some());
+ let inner_has_stats = inner_stat.distinct_count.get_value().is_some()
+ || (inner_stat.min_value.get_value().is_some()
+ && inner_stat.max_value.get_value().is_some());
+ if !outer_has_stats || !inner_has_stats {
+ continue;
+ }
+
+ let outer_ndv = max_distinct_count(outer_num_rows, outer_stat);
+ let inner_ndv = max_distinct_count(inner_num_rows, inner_stat);
+
+ if let (Some(&o), Some(&i)) = (outer_ndv.get_value(), inner_ndv.get_value())
+ && o > 0
+ {
+ selectivity *= (o.min(i) as f64) / (o as f64);
Review Comment:
I've adjusted comment and added test cases
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286684907
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286657778)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286657778-1658-77bg4 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpch
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286678651
๐ค Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/20904#issuecomment-4286664748)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4286664748-1659-x7rvl 6.12.55+ #1 SMP Sun Feb 1 08:59:41 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing use-ndv-for-semi-and-anti-join (5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) to 7acbe03 (merge-base) [diff](https://github.com/apache/datafusion/compare/7acbe03efb853274aac1bdd31c1dfdc8ea647642..5978b00a57f07bbfc470f2cd87cf0a3ffac3bb30) using: tpcds
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: estimate cardinality for semi and anti-joins using distinct counts [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #20904:
URL: https://github.com/apache/datafusion/pull/20904#issuecomment-4286664748
run benchmarks tpcds tpch
```
env:
DATAFUSION_EXECUTION_PARQUET_PUSHDOWN_FILTERS: true
DATAFUSION_EXECUTION_PARQUET_REORDER_FILTERS: true
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org