Details
-
New Feature
-
Status: Stalled (View Workflow)
-
Major
-
Resolution: Unresolved
-
The optimizer could fail to detect an impossible INNER JOIN condition involving IS NULL and a normal equality predicate, causing unnecessary index lookups, joins, and filesort for queries that should return an empty result.
Description
I found a query where the optimizer does not detect an impossible INNER JOIN condition involving IS NULL and a normal equality predicate.
The query condition is logically unsatisfiable:
t1.c0 IS NULL AND t1.c0 = t0.c0 |
Since normal equality = is NULL-rejecting, t1.c0 = t0.c0 can never be TRUE when t1.c0 IS NULL. Therefore, this query should be optimized as an empty result, similar to an "Impossible WHERE" plan.
However, MariaDB still generates and executes normal join plans. In my test case, MariaDB reads NULL-key rows and performs thousands of unnecessary ref lookups even though the result is always empty.
The main run uses optimizer_prune_level=0 to disable heuristic join-order pruning and make the join-order search more exhaustive. This was intended to avoid missing alternative join orders during planning and to expose the performance impact of the missed impossible-condition optimization more clearly. Under this setting, MariaDB still does not detect the impossible condition, and the chosen unhinted plan has a much larger runtime impact.
I also include an additional comparison with optimizer_prune_level=1, where MariaDB chooses a better join order and the runtime is lower. However, even with optimizer_prune_level=1, the impossible condition is still not detected and MariaDB still executes a normal join plan.
Tested Version
12.3.2-MariaDB
|
Environment
MariaDB Server 12.3.2
|
Storage engine: InnoDB
|
OS: Ubuntu 22.04.4 LTS
|
CPU: x86_64, Intel(R) Xeon(R) Gold 5220 CPU @ 2.20GHz
|
|
|
Main reproducer:
|
optimizer_prune_level=0
|
|
|
Additional comparison:
|
optimizer_prune_level=1
|
|
|
Engine-independent statistics collected with:
|
ANALYZE TABLE ... PERSISTENT FOR ALL
|
Reproducer
The full SQL reproducer is attached. The important structure is:
DROP DATABASE IF EXISTS mdev_null_eq_impossible; |
CREATE DATABASE mdev_null_eq_impossible; |
USE mdev_null_eq_impossible; |
|
|
SET SESSION optimizer_prune_level = 0; |
|
|
SELECT VERSION(); |
SHOW VARIABLES LIKE 'optimizer_prune_level'; |
|
|
SET @N_NON_NULL := 50000; |
SET @N_NULL := 2000; |
SET @N_SEQ_LIMIT := 50000; |
|
|
CREATE TABLE t0( |
c0 BIGINT NULL, |
c1 BIGINT, |
c2 DOUBLE, |
c3 VARCHAR(64) |
) ENGINE=InnoDB;
|
|
|
CREATE TABLE t1( |
c0 BIGINT NULL, |
c1 BIGINT, |
c2 DOUBLE, |
c3 VARCHAR(64), |
c4 BIGINT |
) ENGINE=InnoDB;
|
|
|
CREATE TEMPORARY TABLE digits(n INT PRIMARY KEY) ENGINE=Memory; |
INSERT INTO digits VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); |
|
|
CREATE TEMPORARY TABLE seq(n INT PRIMARY KEY) ENGINE=Memory; |
INSERT INTO seq(n) |
SELECT n |
FROM ( |
SELECT d0.n + 10*d1.n + 100*d2.n + 1000*d3.n + 10000*d4.n AS n |
FROM digits d0 |
JOIN digits d1 |
JOIN digits d2 |
JOIN digits d3 |
JOIN digits d4 |
) AS s |
WHERE n < @N_SEQ_LIMIT; |
|
|
INSERT INTO t0(c0, c1, c2, c3) |
SELECT 1000000 + n, |
3000000 + 3*n,
|
n * 1.0,
|
CONCAT('t0_nonnull_', LPAD(n, 5, '0')) |
FROM seq |
WHERE n < @N_NON_NULL; |
|
|
INSERT INTO t1(c0, c1, c2, c3, c4) |
SELECT 1000000 + n, |
3000000 + 3*n,
|
-n * 1.0,
|
CONCAT('t1_nonnull_', LPAD(n, 5, '0')), |
CASE WHEN MOD(n, 3) = 0 THEN NULL ELSE -n END |
FROM seq |
WHERE n < @N_NON_NULL; |
|
|
INSERT INTO t0(c0, c1, c2, c3) |
SELECT NULL, |
-1000000 - n,
|
n * 1.0,
|
CONCAT('t0_null_', LPAD(n, 5, '0')) |
FROM seq |
WHERE n < @N_NULL; |
|
|
INSERT INTO t1(c0, c1, c2, c3, c4) |
SELECT NULL, |
-2000000 - n,
|
-n * 1.0,
|
CONCAT('t1_null_', LPAD(n, 5, '0')), |
NULL |
FROM seq |
WHERE n < @N_NULL; |
|
|
CREATE INDEX i0 ON t0(c0); |
CREATE INDEX i1 ON t0(c0, c1); |
CREATE INDEX i2 ON t1(c0); |
CREATE INDEX i3 ON t1(c0, c1); |
|
|
ANALYZE TABLE t0, t1; |
ANALYZE TABLE t0 PERSISTENT FOR ALL; |
ANALYZE TABLE t1 PERSISTENT FOR ALL; |
Data Sanity Check
The data contains NULL values on both sides:
SELECT COUNT(*) AS t0_rows, SUM(c0 IS NULL) AS t0_null_c0 FROM t0; |
SELECT COUNT(*) AS t1_rows, SUM(c0 IS NULL) AS t1_null_c0 FROM t1; |
Observed result:
t0_rows = 52000, t0_null_c0 = 2000
|
t1_rows = 52000, t1_null_c0 = 2000
|
The normal equality join returns zero rows, as expected:
SELECT COUNT(*) AS eq_join_should_be_zero |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t1.c0 IS NULL; |
Observed result:
eq_join_should_be_zero = 0
|
The NULL-safe equality version confirms that there are actually NULL rows on both sides:
SELECT EXISTS( |
SELECT 1 |
FROM t1 INNER JOIN t0 ON t1.c0 <=> t0.c0 |
WHERE t1.c0 IS NULL |
LIMIT 1
|
) AS null_safe_join_has_rows; |
Observed result:
null_safe_join_has_rows = 1
|
This confirms that the empty result is caused by normal SQL NULL semantics of =, not by lack of NULL values in the data.
Problematic Query
EXPLAIN FORMAT=JSON
|
SELECT t1.c1 AS ref0, t0.c0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t1.c0 IS NULL |
ORDER BY t0.c3 ASC, t0.c0 DESC |
LIMIT 2;
|
|
|
ANALYZE FORMAT=JSON
|
SELECT t1.c1 AS ref0, t0.c0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t1.c0 IS NULL |
ORDER BY t0.c3 ASC, t0.c0 DESC |
LIMIT 2;
|
Actual Behavior with optimizer_prune_level=0
MariaDB does not optimize the query as impossible. Instead, it generates a normal nested-loop/ref plan.
Observed plan excerpt:
{
|
"query_block": {
|
"cost": 590.6931915,
|
"nested_loop": [
|
{
|
"read_sorted_file": {
|
"filesort": {
|
"sort_key": "t0.c3, t0.c0 desc",
|
"table": {
|
"table_name": "t0",
|
"access_type": "ref",
|
"key": "i0",
|
"rows": 2000,
|
"index_condition": "t0.c0 is null",
|
"attached_condition": "t0.c0 <=> NULL"
|
}
|
}
|
}
|
},
|
{
|
"table": {
|
"table_name": "t1",
|
"access_type": "ref",
|
"key": "i3",
|
"loops": 2000,
|
"rows": 2000,
|
"attached_condition": "t1.c0 = t0.c0"
|
}
|
}
|
]
|
}
|
}
|
Observed runtime from ANALYZE FORMAT=JSON:
{
|
"query_block": {
|
"cost": 590.6931915,
|
"r_total_time_ms": 1180.435477,
|
"nested_loop": [
|
{
|
"read_sorted_file": {
|
"filesort": {
|
"r_output_rows": 2000,
|
"table": {
|
"table_name": "t0",
|
"r_rows": 2000,
|
"index_condition": "t0.c0 is null"
|
}
|
}
|
}
|
},
|
{
|
"table": {
|
"table_name": "t1",
|
"r_loops": 2000,
|
"r_rows": 2000,
|
"r_total_filtered": 0,
|
"attached_condition": "t1.c0 = t0.c0",
|
"r_filtered": 0
|
}
|
}
|
]
|
}
|
}
|
The optimizer appears to propagate t1.c0 IS NULL to t0.c0 IS NULL, but it misses that the normal equality predicate t1.c0 = t0.c0 is NULL-rejecting. Therefore, all candidate rows are filtered only during execution.
Performance Impact
Although the query always returns an empty result, MariaDB still executes normal join plans.
With optimizer_prune_level=0, the unhinted query produced:
unhinted query, optimizer_prune_level=0:
|
estimated cost: 590.6931915
|
runtime: 1180.435477 ms
|
The unhinted plan reads 2000 NULL-key rows from t0, performs 2000 ref lookups into t1, and then filters all candidate rows at execution time:
t1:
|
r_loops: 2000
|
r_rows: 2000
|
r_total_filtered: 0
|
attached_condition: t1.c0 = t0.c0
|
r_filtered: 0
|
Forcing the join order with JOIN_ORDER(t1, t0) under optimizer_prune_level=0 gives a higher estimated cost but runs faster:
ANALYZE FORMAT=JSON
|
SELECT /*+ JOIN_ORDER(t1, t0) */ t1.c1 AS ref0, t0.c0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t1.c0 IS NULL |
ORDER BY t0.c3 ASC, t0.c0 DESC |
LIMIT 2;
|
Observed result:
unhinted query, optimizer_prune_level=0:
|
estimated cost: 590.6931915
|
runtime: 1180.435477 ms
|
|
|
JOIN_ORDER(t1, t0), optimizer_prune_level=0:
|
estimated cost: 6723.141002
|
runtime: 276.8652841 ms
|
The hinted query is about 4.26x faster despite having a much higher estimated cost. This shows that optimizer_prune_level=0 can make the runtime impact more severe.
However, this is only secondary evidence. The main issue is not the join-order hint or the cost ranking. The main issue is that both plans should have been avoided entirely, because the condition is logically impossible.
Additional Comparison with optimizer_prune_level=1
I also tested the same query with optimizer_prune_level=1.
With this setting, MariaDB chooses a better join order and the runtime is much lower than the unhinted optimizer_prune_level=0 case. However, the impossible condition is still not detected. MariaDB still generates and executes a normal join plan:
unhinted query, optimizer_prune_level=1:
|
estimated cost: 6723.141002
|
runtime: 276.8174371 ms
|
Observed plan excerpt:
{
|
"query_block": {
|
"cost": 6723.141002,
|
"filesort": {
|
"sort_key": "t0.c3, t0.c0 desc",
|
"temporary_table": {
|
"nested_loop": [
|
{
|
"table": {
|
"table_name": "t1",
|
"access_type": "ref",
|
"key": "i3",
|
"rows": 2000,
|
"attached_condition": "t1.c0 is null"
|
}
|
},
|
{
|
"table": {
|
"table_name": "t0",
|
"access_type": "ref",
|
"key": "i0",
|
"loops": 2000,
|
"rows": 2000,
|
"index_condition": "t0.c0 = t1.c0"
|
}
|
}
|
]
|
}
|
}
|
}
|
}
|
Observed runtime excerpt:
{
|
"query_block": {
|
"cost": 6723.141002,
|
"r_total_time_ms": 276.8174371,
|
"filesort": {
|
"r_output_rows": 0,
|
"temporary_table": {
|
"nested_loop": [
|
{
|
"table": {
|
"table_name": "t1",
|
"r_rows": 2000,
|
"attached_condition": "t1.c0 is null"
|
}
|
},
|
{
|
"table": {
|
"table_name": "t0",
|
"r_loops": 2000,
|
"r_rows": 0,
|
"r_total_filtered": 0,
|
"index_condition": "t0.c0 = t1.c0",
|
"r_icp_filtered": 0
|
}
|
}
|
]
|
}
|
}
|
}
|
}
|
So optimizer_prune_level=1 avoids the slower join order seen with optimizer_prune_level=0, but it still does not optimize the query as impossible/empty. The missed contradiction detection remains.
Expected Behavior
The optimizer should recognize that the condition is unsatisfiable:
t1.c0 IS NULL AND t1.c0 = t0.c0 |
Because normal equality = is NULL-rejecting, the query block should be optimized as an empty result. MariaDB should avoid scanning NULL-key ranges, performing ref lookups, and doing filesort.
Additional Evidence: Not Only ORDER BY/LIMIT
The same issue also appears without ORDER BY and LIMIT:
EXPLAIN FORMAT=JSON
|
SELECT t1.c1 AS ref0, t0.c0 |
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0 |
WHERE t1.c0 IS NULL; |
Observed plan excerpt:
{
|
"query_block": {
|
"cost": 588.6917683,
|
"nested_loop": [
|
{
|
"table": {
|
"table_name": "t1",
|
"access_type": "ref",
|
"key": "i3",
|
"rows": 2000,
|
"attached_condition": "t1.c0 is null"
|
}
|
},
|
{
|
"table": {
|
"table_name": "t0",
|
"access_type": "ref",
|
"key": "i0",
|
"loops": 2000,
|
"rows": 2000,
|
"attached_condition": "t0.c0 = t1.c0"
|
}
|
}
|
]
|
}
|
}
|
Therefore, this does not seem to be only an ORDER BY ... LIMIT planning issue. The more fundamental issue is missed contradiction detection for IS NULL combined with normal equality in an INNER JOIN.
Summary
- The data contains NULL values on both sides.
- t1.c0 IS NULL AND t1.c0 = t0.c0 is logically impossible under normal equality semantics.
- MariaDB does not detect this impossible condition.
- With optimizer_prune_level=1, MariaDB chooses a better plan, but the impossible condition is still not detected.
- With optimizer_prune_level=0, the same missed impossible condition remains and the runtime impact becomes larger.
- The query should be optimized as an empty result.
- The issue also appears without ORDER BY and LIMIT.
