Description:
I found a cardinality and cost estimation inconsistency in the legacy
optimizer when a hash join has a local predicate on its second/probe-side
table.
The attached self-contained testcase creates two tables, a and b, with
100 rows each.
Column k has exactly 10 distinct values, and every value occurs 10 times
in each table. Therefore:
SELECT COUNT(*)
FROM a JOIN b ON a.k = b.k;
returns exactly 1000 rows.
Column x contains every integer from 0 through 99 exactly once. A full
singleton histogram with 100 buckets is created for x.
The baseline hash join is estimated correctly:
actual rows: 1000
final estimated rows: 1000
final estimated cost: 1010.5
However, adding an always-true local predicate to the second/probe-side
table produces an incorrect final hash-join estimate:
SELECT /*+ JOIN_ORDER(a,b) BNL(b) */
a.id, b.id
FROM a
JOIN b ON a.k = b.k
WHERE b.x < 100;
Since b.x contains values 0 through 99, b.x < 100 is true for every row.
The histogram also reports selectivity 1.0 for this predicate.
The optimizer trace correctly estimates the join-enumeration candidate as:
b access resulting rows: 100
local final filtering effect: 1.0
condition filtering percent: 10
rows_for_plan: 1000
cost_for_plan: 1010.5
But the final hash-join AccessPath is estimated as:
table scan on b: 100 rows
Filter(b.x < 100): 10 rows
hash join root: 100 rows
final estimated cost: 110.5
EXPLAIN ANALYZE shows:
actual Filter rows: 100
actual hash join rows: 1000
A selective predicate shows the same issue more clearly:
WHERE b.x < 34
The histogram selectivity is 0.34. The join-enumeration candidate is
correctly estimated as 340 rows:
100 * 34 * 0.10 = 340
However, the final hash-join AccessPath estimates:
Filter(b.x < 34): 3.4 rows
hash join root: 11.56 rows
while the actual result contains 340 rows.
The value 11.56 corresponds to applying the combined effect twice:
local predicate selectivity = 0.34
join selectivity = 0.10
combined effect = 0.034
100 * (100 * 0.034) * 0.034 = 11.56
Control queries do not show this estimate collapse:
1. Disabling hash join with NO_BNL(b) estimates approximately 340 rows.
2. Replacing b.x < 34 with a physically prefiltered 34-row table b34
estimates approximately 340 rows.
3. Moving the same x < 34 predicate to the first/build-side table
estimates approximately 340 rows.
Thus, the issue appears specific to hash-join AccessPath construction
when the second/probe-side table has a local predicate.
The query result is correct. The problem is that estimated_rows and
estimated cost in the final hash-join AccessPath are substantially too
low. This estimate may propagate to parent operators and affect physical
plan or join-order decisions.
How to repeat:
1. Save the attached file as:
mysql_bug_hash_join_double_filter_effect_repro.sql
2. Execute it with a MySQL 9.7.1 client. The --comments option is
required to preserve optimizer hints:
mysql --comments --table --raw -uUSER -p \
< mysql_bug_hash_join_double_filter_effect_repro.sql \
> mysql_bug_hash_join_double_filter_effect_repro.out 2>&1
3. Inspect the "FINAL ACCESSPATH SUMMARY" section.
On my affected MySQL 9.7.1 build, it reports approximately:
scenario actual rows final estimated rows
----------------------- ----------- --------------------
BASE_HASH 1000 1000
TRUE_PROBE_HASH 1000 100
TRUE_PROBE_NO_BNL 1000 1000
SELECTIVE_PROBE_HASH 340 11.56
SELECTIVE_PROBE_NO_BNL 340 340
PHYSICAL_B34_HASH 340 340
SELECTIVE_BUILD_HASH 340 340
4. Inspect the "TRACE CANDIDATE SUMMARY" section.
The join-enumeration estimates are approximately:
TRUE_PROBE_HASH:
rows_for_plan = 1000
access resulting_rows = 100
access final_filtering_effect = 1.0
SELECTIVE_PROBE_HASH:
rows_for_plan = 340
access resulting_rows = 34
access final_filtering_effect = 0.34
Thus the join-enumeration cardinalities are reasonable, but the final
hash-join AccessPath cardinalities become 100 and 11.56 respectively.
5. The file also executes EXPLAIN ANALYZE three times for the important
queries. It consistently shows:
TRUE_PROBE_HASH:
estimated Filter rows = 10
actual Filter rows = 100
estimated join rows = 100
actual join rows = 1000
SELECTIVE_PROBE_HASH:
estimated Filter rows = 3.4
actual Filter rows = 34
estimated join rows = 11.56
actual join rows = 340
Suggested fix:
Please keep the selectivity of local table predicates separate from the
selectivity of hash-join predicates during legacy AccessPath
construction.
For a Filter AccessPath that evaluates only a local condition such as:
b.x < 100
or:
b.x < 34
its output cardinality should use only the local predicate selectivity.
The equality-join selectivity for:
a.k = b.k
should then be applied once at the hash join node.
The current behavior appears to reuse a combined probe-side filter
effect for both:
1. the probe-side Filter AccessPath; and
2. the hash join output cardinality.
If POSITION::filter_effect contains both local and join selectivity,
using it at both nodes can square the combined filtering effect.
A regression test could use:
- two 100-row tables;
- ten equally distributed join-key values;
- an always-true probe-side predicate with histogram selectivity 1.0;
- a 34%-selective probe-side predicate;
- NO_BNL, physical-prefilter, and build-side-filter controls.
The final hash-join estimates should remain consistent with the
join-enumeration estimates: 1000 rows for the always-true case and
approximately 340 rows for the 34%-selective case.
Description: I found a cardinality and cost estimation inconsistency in the legacy optimizer when a hash join has a local predicate on its second/probe-side table. The attached self-contained testcase creates two tables, a and b, with 100 rows each. Column k has exactly 10 distinct values, and every value occurs 10 times in each table. Therefore: SELECT COUNT(*) FROM a JOIN b ON a.k = b.k; returns exactly 1000 rows. Column x contains every integer from 0 through 99 exactly once. A full singleton histogram with 100 buckets is created for x. The baseline hash join is estimated correctly: actual rows: 1000 final estimated rows: 1000 final estimated cost: 1010.5 However, adding an always-true local predicate to the second/probe-side table produces an incorrect final hash-join estimate: SELECT /*+ JOIN_ORDER(a,b) BNL(b) */ a.id, b.id FROM a JOIN b ON a.k = b.k WHERE b.x < 100; Since b.x contains values 0 through 99, b.x < 100 is true for every row. The histogram also reports selectivity 1.0 for this predicate. The optimizer trace correctly estimates the join-enumeration candidate as: b access resulting rows: 100 local final filtering effect: 1.0 condition filtering percent: 10 rows_for_plan: 1000 cost_for_plan: 1010.5 But the final hash-join AccessPath is estimated as: table scan on b: 100 rows Filter(b.x < 100): 10 rows hash join root: 100 rows final estimated cost: 110.5 EXPLAIN ANALYZE shows: actual Filter rows: 100 actual hash join rows: 1000 A selective predicate shows the same issue more clearly: WHERE b.x < 34 The histogram selectivity is 0.34. The join-enumeration candidate is correctly estimated as 340 rows: 100 * 34 * 0.10 = 340 However, the final hash-join AccessPath estimates: Filter(b.x < 34): 3.4 rows hash join root: 11.56 rows while the actual result contains 340 rows. The value 11.56 corresponds to applying the combined effect twice: local predicate selectivity = 0.34 join selectivity = 0.10 combined effect = 0.034 100 * (100 * 0.034) * 0.034 = 11.56 Control queries do not show this estimate collapse: 1. Disabling hash join with NO_BNL(b) estimates approximately 340 rows. 2. Replacing b.x < 34 with a physically prefiltered 34-row table b34 estimates approximately 340 rows. 3. Moving the same x < 34 predicate to the first/build-side table estimates approximately 340 rows. Thus, the issue appears specific to hash-join AccessPath construction when the second/probe-side table has a local predicate. The query result is correct. The problem is that estimated_rows and estimated cost in the final hash-join AccessPath are substantially too low. This estimate may propagate to parent operators and affect physical plan or join-order decisions. How to repeat: 1. Save the attached file as: mysql_bug_hash_join_double_filter_effect_repro.sql 2. Execute it with a MySQL 9.7.1 client. The --comments option is required to preserve optimizer hints: mysql --comments --table --raw -uUSER -p \ < mysql_bug_hash_join_double_filter_effect_repro.sql \ > mysql_bug_hash_join_double_filter_effect_repro.out 2>&1 3. Inspect the "FINAL ACCESSPATH SUMMARY" section. On my affected MySQL 9.7.1 build, it reports approximately: scenario actual rows final estimated rows ----------------------- ----------- -------------------- BASE_HASH 1000 1000 TRUE_PROBE_HASH 1000 100 TRUE_PROBE_NO_BNL 1000 1000 SELECTIVE_PROBE_HASH 340 11.56 SELECTIVE_PROBE_NO_BNL 340 340 PHYSICAL_B34_HASH 340 340 SELECTIVE_BUILD_HASH 340 340 4. Inspect the "TRACE CANDIDATE SUMMARY" section. The join-enumeration estimates are approximately: TRUE_PROBE_HASH: rows_for_plan = 1000 access resulting_rows = 100 access final_filtering_effect = 1.0 SELECTIVE_PROBE_HASH: rows_for_plan = 340 access resulting_rows = 34 access final_filtering_effect = 0.34 Thus the join-enumeration cardinalities are reasonable, but the final hash-join AccessPath cardinalities become 100 and 11.56 respectively. 5. The file also executes EXPLAIN ANALYZE three times for the important queries. It consistently shows: TRUE_PROBE_HASH: estimated Filter rows = 10 actual Filter rows = 100 estimated join rows = 100 actual join rows = 1000 SELECTIVE_PROBE_HASH: estimated Filter rows = 3.4 actual Filter rows = 34 estimated join rows = 11.56 actual join rows = 340 Suggested fix: Please keep the selectivity of local table predicates separate from the selectivity of hash-join predicates during legacy AccessPath construction. For a Filter AccessPath that evaluates only a local condition such as: b.x < 100 or: b.x < 34 its output cardinality should use only the local predicate selectivity. The equality-join selectivity for: a.k = b.k should then be applied once at the hash join node. The current behavior appears to reuse a combined probe-side filter effect for both: 1. the probe-side Filter AccessPath; and 2. the hash join output cardinality. If POSITION::filter_effect contains both local and join selectivity, using it at both nodes can square the combined filtering effect. A regression test could use: - two 100-row tables; - ten equally distributed join-key values; - an always-true probe-side predicate with histogram selectivity 1.0; - a 34%-selective probe-side predicate; - NO_BNL, physical-prefilter, and build-side-filter controls. The final hash-join estimates should remain consistent with the join-enumeration estimates: 1000 rows for the always-true case and approximately 340 rows for the 34%-selective case.