Description:
With hypergraph_optimizer=ON and derived_merge=OFF, a correlated LATERAL
derived table that gets materialized (and is then accessed via a ref/index
lookup) is mis-evaluated: a derived table that should be non-empty is computed
as empty, producing wrong results. The other three optimizer_switch
combinations (hg=ON+merge=ON, hg=OFF+merge=ON, hg=OFF+merge=OFF) all produce
the correct row content for the same query.
Root cause analysis
-------------------
A node's lateral_dependencies() is an intrinsic property of the node,
independent of the chosen access method; every access path of that node must
carry it in parameter_tables. Otherwise the join enumerator will not force the
node to be re-driven per outer row, and AllowHashJoin() will not forbid hashing
it onto the build side.
Community code merges lateral_dependencies() into parameter_tables in exactly
one place — the full-table-scan proposer
CostingReceiver::ProposeAccessPathForBaseTable():
path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies();
The index/ref proposer CostingReceiver::ProposeAccessPathForIndex() — like the
range/index-merge/skip-scan proposers — has no such merge. For a ref path,
RefAccessBuilder::MakePath() derives parameter_tables from the key match only:
path.parameter_tables = GetNodeMapFromTableMap(
key_match.parameter_tables & ~m_table->pos_in_table_list->map(),
graph()->table_num_to_node_num);
In this query the lookup key on the materialized table is a = g_t1.a, so the
ref path gets parameter_tables = {g_t1} — the derived table's own lateral
dependencies {g_t9, g_t0} are dropped.
Chain of consequences:
1. Ref/materialize path for dt: parameter_tables = {g_t1} (missing {g_t9, g_t0}).
2. NLJ path {g_t1, dt}: parameter_tables = {g_t1} & ~{g_t1, dt} = {}.
3. Joining {g_t9, g_t0} with {g_t1, dt}: AllowHashJoin() checks
if (Overlaps(left_path.parameter_tables, right) ||
Overlaps(right_path.parameter_tables, left | RAND_TABLE_BIT)) return false;
Overlaps({}, {g_t9, g_t0}) is false, so the hash join is not rejected.
4. The cost model then picks a hash join: {g_t1, dt} goes to the build side and
is materialized once, while g_t9/g_t0 are only read later on the probe side.
5. dt's correlation predicate g_t9.x = g_t0.x is evaluated against unbound
tables, is never true, dt is always empty, and wrong results are returned.
In short: when the hypergraph optimizer builds a ref/index path for a
materialized LATERAL derived table, ProposeAccessPathForIndex forgets to add
the node's lateral dependencies, so the access path's parameter_tables loses
the outer tables, and the optimizer wrongly materializes the derived table
"once / hash-joined" instead of "re-materialized per outer row".
How to repeat:
How to repeat:
The bug is cost-model dependent: the chosen plan must materialize the LATERAL
derived table and access it via a ref/auto-key lookup (rather than an inline
nested loop). A small data set picks a safe plan; enlarging the derived table's
source (~1000 rows) makes the materialize+ref plan cheaper and exposes the bug.
The script below sets that up deterministically.
SET cte_max_recursion_depth = 100000;
DROP TABLE IF EXISTS g_t9, g_t0, g_t1, g_t2;
CREATE TABLE g_t9 (x INT);
CREATE TABLE g_t0 (x INT);
CREATE TABLE g_t1 (a INT);
CREATE TABLE g_t2 (a INT);
INSERT INTO g_t9 VALUES (1),(2);
INSERT INTO g_t0 VALUES (1),(3);
INSERT INTO g_t1 VALUES (10),(20);
INSERT INTO g_t2 VALUES (10),(30);
-- Enlarge the derived table's source so that
-- "materialize g_t2 + auto_key ref lookup" beats "inline NLJ",
-- making the cost model pick the buggy access path.
INSERT INTO g_t2
SELECT 1000 + seq
FROM (WITH RECURSIVE g(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM g WHERE n < 1000)
SELECT n AS seq FROM g) s;
ANALYZE TABLE g_t9, g_t0, g_t1, g_t2;
SET optimizer_switch = 'hypergraph_optimizer=on,derived_merge=off';
SELECT g_t9.x, g_t0.x, g_t1.a, dt.a
FROM g_t9 JOIN g_t0 ON TRUE
LEFT JOIN ( g_t1 LEFT JOIN LATERAL
( SELECT g_t2.a FROM g_t2 WHERE g_t9.x = g_t0.x ) AS dt
ON dt.a = g_t1.a ) ON TRUE;
Expected behavior
-----------------
The derived table dt is non-empty only when g_t9.x = g_t0.x (in that case dt is
all of g_t2). With g_t9={1,2} and g_t0={1,3}, the only matching combination is
(1,1); then dt contains a=10, which matches g_t1.a=10. So exactly one row
should have a non-NULL dt.a: (1, 1, 10, 10).
Ground truth (hypergraph_optimizer=off, derived_merge=off) is correct —
exactly one non-NULL row:
+------+------+------+------+
| t9 | t0 | t1 | a |
+------+------+------+------+
| 1 | 1 | 10 | 10 |
| 1 | 1 | 20 | NULL |
| 1 | 3 | 10 | NULL |
| 1 | 3 | 20 | NULL |
| 2 | 1 | 10 | NULL |
| 2 | 1 | 20 | NULL |
| 2 | 3 | 10 | NULL |
| 2 | 3 | 20 | NULL |
+------+------+------+------+
Actual behavior (wrong)
-----------------------
With hypergraph_optimizer=on, derived_merge=off, all 8 rows have dt.a IS NULL —
the (1,1,10,10) row content is lost:
+------+------+------+------+
| t9 | t0 | t1 | a |
+------+------+------+------+
| 1 | 1 | 10 | NULL |
| 1 | 1 | 20 | NULL |
| 1 | 3 | 10 | NULL |
| 1 | 3 | 20 | NULL |
| 2 | 1 | 10 | NULL |
| 2 | 1 | 20 | NULL |
| 2 | 3 | 10 | NULL |
| 2 | 3 | 20 | NULL |
+------+------+------+------+
Aggregate check:
optimizer_switch | COUNT(*) | SUM(dt.a IS NOT NULL) | verdict
--------------------------------------------+----------+----------------------+---------------------------------
hypergraph_optimizer=on, derived_merge=off | 8 | 0 | wrong - (1,1,10,10) lost
hypergraph_optimizer=off, derived_merge=off | 8 | 1 | correct
Plan comparison (EXPLAIN FORMAT=TREE)
-------------------------------------
Bad plan (hypergraph_optimizer=on, derived_merge=off):
-> Left hash join (no condition), extra conditions: true (cost=2436..2502 rows=802)
-> Inner hash join (no condition) (cost=1.49..2.21 rows=4)
-> Table scan on g_t9 (cost=0.295..0.59 rows=2)
-> Hash
-> Table scan on g_t0 (cost=0.295..0.59 rows=2)
-> Hash
-> Nested loop left join (cost=1190..2368 rows=200)
-> Table scan on g_t1 (cost=0.295..0.59 rows=2)
-> Covering index lookup on dt using <auto_key0> (a = g_t1.a) (cost=1184..1184 rows=100)
-> Temporary table (cost=1184..1184 rows=1002)
-> Filter: (g_t9.x = g_t0.x) (cost=0.353..353 rows=1002)
-> Table scan on g_t2 (cost=0.295..296 rows=1002)
What goes wrong:
1. The {g_t1, dt} subtree is placed on the build (Hash) side of the outer
Left hash join; by hash-join semantics, the build side is produced once,
before the probe side is read.
2. But dt's materialization carries Filter: (g_t9.x = g_t0.x), and g_t9/g_t0
live on the probe side — not yet bound when the build side is produced.
3. The predicate therefore evaluates against unbound values (never true), so
dt is always empty, every dt.a is NULL, and (1,1,10,10) is lost.
Correct plan (hypergraph_optimizer=off, derived_merge=off): g_t9/g_t0 drive the
nested loop from the outside, and dt is re-materialized per outer row — note
the explicit invalidation:
-> Nested loop left join (cost=804 rows=8016)
-> Nested loop inner join (cost=1.35 rows=4)
-> Table scan on g_t9 (cost=0.45 rows=2)
-> Invalidate materialized tables (row from g_t0) (cost=0.35 rows=2)
-> Table scan on g_t0 (cost=0.35 rows=2)
-> Nested loop left join (cost=321 rows=2004)
-> Table scan on g_t1 (cost=0.3 rows=2)
-> Covering index lookup on dt using <auto_key0> (a = g_t1.a) (cost=334..347 rows=10)
-> Materialize (invalidate on row from g_t0) (cost=332..332 rows=1002)
-> Filter: (g_t9.x = g_t0.x) (cost=101 rows=1002)
-> Table scan on g_t2 (cost=101 rows=1002)
Suggested fix:
lateral_dependencies() must be merged into parameter_tables for every
single-table access path, not only full scans. The natural place is
CostingReceiver::ApplyPredicatesForBaseTable() — the single common funnel used
by all single-table access proposers (table scan, ordered range,
ROR-intersect, ROR-union, index-merge, skip-scan, index-ref, base-scan).
The fix is a one-line move: delete the merge from
ProposeAccessPathForBaseTable() and add it in ApplyPredicatesForBaseTable():
diff --git a/sql/join_optimizer/join_optimizer.cc b/sql/join_optimizer/join_optimizer.cc
index 9147fc56863..385c6bb16a4 100644
--- a/sql/join_optimizer/join_optimizer.cc
+++ b/sql/join_optimizer/join_optimizer.cc
@@ -4351,7 +4351,6 @@ void CostingReceiver::ProposeAccessPathForBaseTable(
&new_fd_set);
path->ordering_state =
m_orderings->ApplyFDs(path->ordering_state, new_fd_set);
- path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies();
ProposeAccessPathWithOrderings(
TableBitmap(node_idx), new_fd_set, /*obsolete_orderings=*/0, path,
materialize_subqueries ? "mat. subq" : description_for_trace);
@@ -4427,6 +4426,23 @@ void CostingReceiver::ApplyPredicatesForBaseTable(
double materialize_cost = 0.0;
const NodeMap my_map = TableBitmap(node_idx);
+
+ // A node may carry lateral dependencies on outer tables it references: a
+ // LATERAL derived table / table function (via Query_expression::m_lateral_deps),
+ // or even a regular table whose in-subtree join conditions reference
+ // out-of-subtree tables (see FindLateralDependencies()). Those dependencies
+ // must be reflected in parameter_tables for EVERY access path of the node, so
+ // the join enumerator re-drives the node per outer row (and AllowHashJoin()
+ // forbids hashing it against its lateral dependency). This is the single
+ // choke point shared by all single-table access proposers (table scan, ref,
+ // index, range, index-merge, skip-scan); applying it here keeps every access
+ // method consistent. Without it, e.g. an index/ref or range access into a
+ // materialized correlated LATERAL derived table would drop the dependency
+ // (its parameter_tables come only from the key/range match) and the table
+ // could be wrongly materialized once - producing stale or empty results for
+ // correlated LATERAL derived tables with derived_merge=off.
+ path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies();
+
set_count_examined_rows(path, true);
path->set_num_output_rows(path->num_output_rows_before_filter);
path->set_cost(path->cost_before_filter());
Verified on 9.7.2: with this fix, the reproducing query returns the correct
nonnull=1 under hypergraph_optimizer=on,derived_merge=off (was 0), and all
hypergraph_* MTR tests pass.
Description: With hypergraph_optimizer=ON and derived_merge=OFF, a correlated LATERAL derived table that gets materialized (and is then accessed via a ref/index lookup) is mis-evaluated: a derived table that should be non-empty is computed as empty, producing wrong results. The other three optimizer_switch combinations (hg=ON+merge=ON, hg=OFF+merge=ON, hg=OFF+merge=OFF) all produce the correct row content for the same query. Root cause analysis ------------------- A node's lateral_dependencies() is an intrinsic property of the node, independent of the chosen access method; every access path of that node must carry it in parameter_tables. Otherwise the join enumerator will not force the node to be re-driven per outer row, and AllowHashJoin() will not forbid hashing it onto the build side. Community code merges lateral_dependencies() into parameter_tables in exactly one place — the full-table-scan proposer CostingReceiver::ProposeAccessPathForBaseTable(): path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies(); The index/ref proposer CostingReceiver::ProposeAccessPathForIndex() — like the range/index-merge/skip-scan proposers — has no such merge. For a ref path, RefAccessBuilder::MakePath() derives parameter_tables from the key match only: path.parameter_tables = GetNodeMapFromTableMap( key_match.parameter_tables & ~m_table->pos_in_table_list->map(), graph()->table_num_to_node_num); In this query the lookup key on the materialized table is a = g_t1.a, so the ref path gets parameter_tables = {g_t1} — the derived table's own lateral dependencies {g_t9, g_t0} are dropped. Chain of consequences: 1. Ref/materialize path for dt: parameter_tables = {g_t1} (missing {g_t9, g_t0}). 2. NLJ path {g_t1, dt}: parameter_tables = {g_t1} & ~{g_t1, dt} = {}. 3. Joining {g_t9, g_t0} with {g_t1, dt}: AllowHashJoin() checks if (Overlaps(left_path.parameter_tables, right) || Overlaps(right_path.parameter_tables, left | RAND_TABLE_BIT)) return false; Overlaps({}, {g_t9, g_t0}) is false, so the hash join is not rejected. 4. The cost model then picks a hash join: {g_t1, dt} goes to the build side and is materialized once, while g_t9/g_t0 are only read later on the probe side. 5. dt's correlation predicate g_t9.x = g_t0.x is evaluated against unbound tables, is never true, dt is always empty, and wrong results are returned. In short: when the hypergraph optimizer builds a ref/index path for a materialized LATERAL derived table, ProposeAccessPathForIndex forgets to add the node's lateral dependencies, so the access path's parameter_tables loses the outer tables, and the optimizer wrongly materializes the derived table "once / hash-joined" instead of "re-materialized per outer row". How to repeat: How to repeat: The bug is cost-model dependent: the chosen plan must materialize the LATERAL derived table and access it via a ref/auto-key lookup (rather than an inline nested loop). A small data set picks a safe plan; enlarging the derived table's source (~1000 rows) makes the materialize+ref plan cheaper and exposes the bug. The script below sets that up deterministically. SET cte_max_recursion_depth = 100000; DROP TABLE IF EXISTS g_t9, g_t0, g_t1, g_t2; CREATE TABLE g_t9 (x INT); CREATE TABLE g_t0 (x INT); CREATE TABLE g_t1 (a INT); CREATE TABLE g_t2 (a INT); INSERT INTO g_t9 VALUES (1),(2); INSERT INTO g_t0 VALUES (1),(3); INSERT INTO g_t1 VALUES (10),(20); INSERT INTO g_t2 VALUES (10),(30); -- Enlarge the derived table's source so that -- "materialize g_t2 + auto_key ref lookup" beats "inline NLJ", -- making the cost model pick the buggy access path. INSERT INTO g_t2 SELECT 1000 + seq FROM (WITH RECURSIVE g(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM g WHERE n < 1000) SELECT n AS seq FROM g) s; ANALYZE TABLE g_t9, g_t0, g_t1, g_t2; SET optimizer_switch = 'hypergraph_optimizer=on,derived_merge=off'; SELECT g_t9.x, g_t0.x, g_t1.a, dt.a FROM g_t9 JOIN g_t0 ON TRUE LEFT JOIN ( g_t1 LEFT JOIN LATERAL ( SELECT g_t2.a FROM g_t2 WHERE g_t9.x = g_t0.x ) AS dt ON dt.a = g_t1.a ) ON TRUE; Expected behavior ----------------- The derived table dt is non-empty only when g_t9.x = g_t0.x (in that case dt is all of g_t2). With g_t9={1,2} and g_t0={1,3}, the only matching combination is (1,1); then dt contains a=10, which matches g_t1.a=10. So exactly one row should have a non-NULL dt.a: (1, 1, 10, 10). Ground truth (hypergraph_optimizer=off, derived_merge=off) is correct — exactly one non-NULL row: +------+------+------+------+ | t9 | t0 | t1 | a | +------+------+------+------+ | 1 | 1 | 10 | 10 | | 1 | 1 | 20 | NULL | | 1 | 3 | 10 | NULL | | 1 | 3 | 20 | NULL | | 2 | 1 | 10 | NULL | | 2 | 1 | 20 | NULL | | 2 | 3 | 10 | NULL | | 2 | 3 | 20 | NULL | +------+------+------+------+ Actual behavior (wrong) ----------------------- With hypergraph_optimizer=on, derived_merge=off, all 8 rows have dt.a IS NULL — the (1,1,10,10) row content is lost: +------+------+------+------+ | t9 | t0 | t1 | a | +------+------+------+------+ | 1 | 1 | 10 | NULL | | 1 | 1 | 20 | NULL | | 1 | 3 | 10 | NULL | | 1 | 3 | 20 | NULL | | 2 | 1 | 10 | NULL | | 2 | 1 | 20 | NULL | | 2 | 3 | 10 | NULL | | 2 | 3 | 20 | NULL | +------+------+------+------+ Aggregate check: optimizer_switch | COUNT(*) | SUM(dt.a IS NOT NULL) | verdict --------------------------------------------+----------+----------------------+--------------------------------- hypergraph_optimizer=on, derived_merge=off | 8 | 0 | wrong - (1,1,10,10) lost hypergraph_optimizer=off, derived_merge=off | 8 | 1 | correct Plan comparison (EXPLAIN FORMAT=TREE) ------------------------------------- Bad plan (hypergraph_optimizer=on, derived_merge=off): -> Left hash join (no condition), extra conditions: true (cost=2436..2502 rows=802) -> Inner hash join (no condition) (cost=1.49..2.21 rows=4) -> Table scan on g_t9 (cost=0.295..0.59 rows=2) -> Hash -> Table scan on g_t0 (cost=0.295..0.59 rows=2) -> Hash -> Nested loop left join (cost=1190..2368 rows=200) -> Table scan on g_t1 (cost=0.295..0.59 rows=2) -> Covering index lookup on dt using <auto_key0> (a = g_t1.a) (cost=1184..1184 rows=100) -> Temporary table (cost=1184..1184 rows=1002) -> Filter: (g_t9.x = g_t0.x) (cost=0.353..353 rows=1002) -> Table scan on g_t2 (cost=0.295..296 rows=1002) What goes wrong: 1. The {g_t1, dt} subtree is placed on the build (Hash) side of the outer Left hash join; by hash-join semantics, the build side is produced once, before the probe side is read. 2. But dt's materialization carries Filter: (g_t9.x = g_t0.x), and g_t9/g_t0 live on the probe side — not yet bound when the build side is produced. 3. The predicate therefore evaluates against unbound values (never true), so dt is always empty, every dt.a is NULL, and (1,1,10,10) is lost. Correct plan (hypergraph_optimizer=off, derived_merge=off): g_t9/g_t0 drive the nested loop from the outside, and dt is re-materialized per outer row — note the explicit invalidation: -> Nested loop left join (cost=804 rows=8016) -> Nested loop inner join (cost=1.35 rows=4) -> Table scan on g_t9 (cost=0.45 rows=2) -> Invalidate materialized tables (row from g_t0) (cost=0.35 rows=2) -> Table scan on g_t0 (cost=0.35 rows=2) -> Nested loop left join (cost=321 rows=2004) -> Table scan on g_t1 (cost=0.3 rows=2) -> Covering index lookup on dt using <auto_key0> (a = g_t1.a) (cost=334..347 rows=10) -> Materialize (invalidate on row from g_t0) (cost=332..332 rows=1002) -> Filter: (g_t9.x = g_t0.x) (cost=101 rows=1002) -> Table scan on g_t2 (cost=101 rows=1002) Suggested fix: lateral_dependencies() must be merged into parameter_tables for every single-table access path, not only full scans. The natural place is CostingReceiver::ApplyPredicatesForBaseTable() — the single common funnel used by all single-table access proposers (table scan, ordered range, ROR-intersect, ROR-union, index-merge, skip-scan, index-ref, base-scan). The fix is a one-line move: delete the merge from ProposeAccessPathForBaseTable() and add it in ApplyPredicatesForBaseTable(): diff --git a/sql/join_optimizer/join_optimizer.cc b/sql/join_optimizer/join_optimizer.cc index 9147fc56863..385c6bb16a4 100644 --- a/sql/join_optimizer/join_optimizer.cc +++ b/sql/join_optimizer/join_optimizer.cc @@ -4351,7 +4351,6 @@ void CostingReceiver::ProposeAccessPathForBaseTable( &new_fd_set); path->ordering_state = m_orderings->ApplyFDs(path->ordering_state, new_fd_set); - path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies(); ProposeAccessPathWithOrderings( TableBitmap(node_idx), new_fd_set, /*obsolete_orderings=*/0, path, materialize_subqueries ? "mat. subq" : description_for_trace); @@ -4427,6 +4426,23 @@ void CostingReceiver::ApplyPredicatesForBaseTable( double materialize_cost = 0.0; const NodeMap my_map = TableBitmap(node_idx); + + // A node may carry lateral dependencies on outer tables it references: a + // LATERAL derived table / table function (via Query_expression::m_lateral_deps), + // or even a regular table whose in-subtree join conditions reference + // out-of-subtree tables (see FindLateralDependencies()). Those dependencies + // must be reflected in parameter_tables for EVERY access path of the node, so + // the join enumerator re-drives the node per outer row (and AllowHashJoin() + // forbids hashing it against its lateral dependency). This is the single + // choke point shared by all single-table access proposers (table scan, ref, + // index, range, index-merge, skip-scan); applying it here keeps every access + // method consistent. Without it, e.g. an index/ref or range access into a + // materialized correlated LATERAL derived table would drop the dependency + // (its parameter_tables come only from the key/range match) and the table + // could be wrongly materialized once - producing stale or empty results for + // correlated LATERAL derived tables with derived_merge=off. + path->parameter_tables |= m_graph->nodes[node_idx].lateral_dependencies(); + set_count_examined_rows(path, true); path->set_num_output_rows(path->num_output_rows_before_filter); path->set_cost(path->cost_before_filter()); Verified on 9.7.2: with this fix, the reproducing query returns the correct nonnull=1 under hypergraph_optimizer=on,derived_merge=off (was 0), and all hypergraph_* MTR tests pass.