Cost model chooses much slower lower-cost join order over faster higher-cost plans when optimizer_prune_level=0

Summary

I found a reproducible optimizer performance issue in MariaDB 12.3.2.

With optimizer_prune_level=0, the optimizer appears to misrank join orders: it estimates a slow fanout-first plan as cheaper and chooses it, while estimating much faster early-reject plans as more expensive.

In the reproduced case, the optimizer-chosen plan has estimated cost 18780.77009 and takes about 11531 ms. A forced early-reject plan has a higher estimated cost, 30758.89383, but finishes in about 5.26 ms. Another forced plan has estimated cost 58600.96749 and finishes in about 10.46 ms.

The query result is empty. The slow chosen plan first joins t3 and t2, producing a large intermediate fanout, and only then probes t1 10,000,000 times. All those t1 ref lookups return zero rows. The faster higher-cost plans probe t1 earlier and terminate almost immediately.

This issue is observed with optimizer_prune_level=0. I am reporting it because the full/no-prune search appears to expose a severe cost-model misranking: the optimizer chooses the lowest estimated-cost plan, but that plan is the slowest by several orders of magnitude.

Schema and data pattern

The testcase has three InnoDB tables: t1, t2, and t3.

The data is constructed as follows:

t1 has 2000 rows, with c0 values in the range 1000000..1000499.
t2 has 10000 rows, with c0 values only in 0..4.
t3 has 5000 rows, with c0 values only in 0..4.

Therefore:

t2 JOIN t3 on c0 has 10,000,000 matching rows.
t2 JOIN t1 on c0 has 0 matching rows.
t3 JOIN t1 on c0 has 0 matching rows.
The final query result is empty.

This means that a good join order should probe t1 early and terminate quickly. However, with optimizer_prune_level=0, MariaDB chooses a plan that first joins t3 and t2, producing a huge intermediate fanout, and only then probes t1 10,000,000 times. All those t1 ref lookups return zero rows.

Query

SELECT DISTINCT t2.c4 AS ref0, t3.c2, t2.c5

FROM t2

INNER JOIN t1 ON t2.c0 = t1.c0

INNER JOIN t3 ON t1.c0 = t3.c0

ORDER BY t3.c2 DESC

LIMIT 8;

Observed bad plan

With optimizer_prune_level=0, the base query chooses the following join order:

t3 -> t2 -> t1

EXPLAIN FORMAT=JSON reports the following estimated cost:

cost = 18780.77009

ANALYZE FORMAT=JSON shows:

r_total_time_ms = 11531.47646

The important part is the last t1 lookup:

t1.r_loops = 10000000

t1.r_rows = 0

t1.pages_accessed = 20000000

So the chosen plan performs 10 million failed ref lookups into t1.

Forced faster plan 1

With this hint:

SELECT /*+ JOIN_ORDER(t2, t1, t3) */ DISTINCT t2.c4 AS ref0, t3.c2, t2.c5

FROM t2

INNER JOIN t1 ON t2.c0 = t1.c0

INNER JOIN t3 ON t1.c0 = t3.c0

ORDER BY t3.c2 DESC

LIMIT 8;

EXPLAIN FORMAT=JSON reports a higher estimated cost:

cost = 58600.96749

However, ANALYZE FORMAT=JSON shows:

r_total_time_ms = 10.45576429

This plan probes t1 after scanning t2:

t1.r_loops = 10000

t1.r_rows = 0

t3.r_loops = 0

The third table is never executed because t1 rejects all rows.

Forced faster plan 2

With this hint:

SELECT /*+ JOIN_ORDER(t3, t1, t2) */ DISTINCT t2.c4 AS ref0, t3.c2, t2.c5

FROM t2

INNER JOIN t1 ON t2.c0 = t1.c0

INNER JOIN t3 ON t1.c0 = t3.c0

ORDER BY t3.c2 DESC

LIMIT 8;

EXPLAIN FORMAT=JSON reports:

cost = 30758.89383

But ANALYZE FORMAT=JSON shows:

r_total_time_ms = 5.25837327

This is more than 2000x faster than the optimizer-chosen plan, despite the optimizer estimating it as more expensive.

Control with optimizer_prune_level=1 and optimizer_prune_level=2

Interestingly, both optimizer_prune_level=1 and optimizer_prune_level=2 avoid the bad plan and choose the early-reject join order:

t3 -> t1 -> t2

Both finish in about 5 ms.

So this does not look like a case where pruning removes a good plan. Instead, optimizer_prune_level=0 appears to expose a cost-model misranking: the full/no-prune search chooses the lower estimated cost plan, but that plan is much worse in actual runtime.

Optimizer trace

The optimizer trace confirms that the chosen best join order is:

best_join_order = ["t3", "t2", "t1"]

cost = 18780.77009

The early-reject alternatives are estimated as more expensive, even though they are much faster at runtime. In other words, the estimated-cost ranking is the opposite of the actual-runtime ranking: the lowest-cost plan is the slowest, while the higher-cost plans are much faster.

Expected behavior

The optimizer should prefer a join order that probes t1 earlier, or at least should not rank the t3 -> t2 -> t1 plan as cheaper when the t1 ref lookup rejects all rows. At minimum, the cost model should not rank a plan that performs 10,000,000 failed ref lookups as cheaper than plans that probe the empty/ref-rejecting table earlier and stop after only 5,000 or 10,000 failed lookups.

The issue appears to be that the cost model does not sufficiently account for the disjoint value domains of the join keys, or at least does not propagate this information into the join-order cost ranking.

t1.c0 is in 1000000..1000499

t2.c0 and t3.c0 are in 0..4

As a result, it estimates t1 ref lookups as rows=4, while in reality all lookups return zero rows.

Reproducibility

The attached SQL file creates the schema, inserts deterministic data, collects statistics, runs EXPLAIN FORMAT=JSON and ANALYZE FORMAT=JSON for the base query and forced join orders, and prints optimizer trace output.