ORDER BY join-order costing overcosts sort-before-join plan, causing ~8x slowdown

Summary

I found a reproducible optimizer performance issue on MariaDB 12.3.2.

For a three-table INNER JOIN with ORDER BY, the optimizer chooses:

t3 -> t1 -> t0

  -> filesort

The selected plan materializes the joined result and sorts about 6.3 million rows.

Its estimated cost is:

2165.444633

Three ANALYZE FORMAT=JSON executions take:

19477.663 ms

18778.653 ms

19432.592 ms

Median:

19432.592 ms

Forcing the alternative join order:

t1 -> t3 -> t0

produces a very different ORDER BY strategy: MariaDB sorts only the 502-row t1 input first, then performs the nested-loop joins.

This alternative has a higher estimated cost:

2249.918896

but its three runtimes are:

2234.385 ms

2565.211 ms

2389.387 ms

Median:

2389.387 ms

Thus, the plan estimated as about 3.9% more expensive is actually about 8.13x faster.

Reproducer

Run the attached setup file first:

mariadb < 01_setup.sql

Then run the query test:

mariadb < 02_query_test_with_trace.sql > query_test_with_trace.out 2>&1

The main query is:

SELECT t1.c1 AS ref0

FROM t3

JOIN t0 ON t3.c1 = t0.c0

JOIN t1 ON t3.c0 = t1.c0

ORDER BY t1.c1 DESC;

The diagnostic alternative fixes the join order:

SELECT t1.c1 AS ref0

FROM t1

STRAIGHT_JOIN t3 ON t3.c0 = t1.c0

STRAIGHT_JOIN t0 ON t3.c1 = t0.c0

ORDER BY t1.c1 DESC;

Default plan

The optimizer chooses:

t3 full scan

  -> t1 ref lookup

  -> t0 ref lookup

  -> filesort

Estimated cost:

2165.444633

ANALYZE FORMAT=JSON shows:

filesort:

  r_output_rows: 6303964

  r_sort_passes: 12

Three runtimes:

19477.663 ms

18778.653 ms

19432.592 ms

median: 19432.592 ms

Faster alternative

Forcing:

t1 -> t3 -> t0

produces:

filesort t1

  -> t3 ref lookup

  -> t0 ref lookup

Only the outer t1 input is sorted:

filesort:

  r_output_rows: 502

The sorting operation itself takes less than 1 ms in the measured executions.

Estimated cost:

2249.918896

Three runtimes:

2234.385 ms

2565.211 ms

2389.387 ms

median: 2389.387 ms

The alternative is approximately 8.13x faster despite being assigned a higher estimated cost.

Optimizer trace / possible root cause

I also collected optimizer trace with:

SET optimizer_prune_level=0;

The trace shows that the faster t1 -> t3 -> t0 join order is explicitly considered, so this is not simply a case where heuristic pruning removes the good join order.

For t1 -> t3 -> t0, the trace reports:

plan_prefix: "t1,t3"

table: "t0"

rows_for_plan: 2642528

cost_for_plan: 439.3101042

cost_for_sorting: 1810.608792

giving the final cost:

2249.918896

For the selected t3 -> t1 -> t0 order, the trace reports:

plan_prefix: "t3,t1"

table: "t0"

rows_for_plan: 2542230

cost_for_plan: 423.9419111

cost_for_sorting: 1741.502722

giving:

2165.444633

and the trace selects:

best_join_order: ["t3", "t1", "t0"]

The notable point is that cost_for_sorting for both alternatives closely follows the estimated final join cardinality.

However, the executable t1-first plan does not sort the final joined result.

EXPLAIN FORMAT=JSON for that plan shows:

read_sorted_file

  filesort

    table: t1

    rows: 502

and ANALYZE FORMAT=JSON confirms that only 502 rows are actually sorted before the joins.

The optimizer trace for the forced t1 -> t3 -> t0 plan still reports:

rows_for_plan: 2642528

cost_for_plan: 439.3101042

cost_for_sorting: 1810.608792

even though its physical plan sorts only the 502-row outer table.

This suggests that join-order costing charges the t1-first alternative a sorting cost based on the estimated final join cardinality, while the final executable plan can satisfy ORDER BY by sorting only the small outer table before the joins.

As a result, the sort-before-join benefit is not reflected correctly in the join-order ranking, and the optimizer selects the much slower plan.

ORDER BY control

Removing ORDER BY while keeping the same joins gives:

r_total_time_ms: 2180.044

This is close to the approximately 2.39-second median of the t1-first plan with ORDER BY.

Therefore, the large slowdown is specifically associated with sort placement:

Selected plan:

  join first

  -> sort 6,303,964 rows

Faster plan:

  sort 502 rows

  -> join

optimizer_prune_level control

Setting:

SET optimizer_prune_level=0;

does not change the selected plan.

The optimizer still chooses:

t3 -> t1 -> t0

  -> filesort

with cost:

2165.444633

The optimizer trace also explicitly contains the t1 -> t3 -> t0 alternative.

Therefore, the issue appears to be in cost ranking rather than heuristic join-order pruning.

Expected behavior

The optimizer should account for the physical ordering property of the t1-first plan.

Since ORDER BY can be satisfied by sorting only the 502-row outer table before the joins, this plan should not be charged a sorting cost comparable to sorting the estimated multi-million-row final join result.

The optimizer should either choose the t1 -> t3 -> t0 plan or estimate its cost lower than the plan that sorts the full joined result.

Actual behavior

The optimizer assigns the t1-first plan a higher estimated cost and selects t3 -> t1 -> t0.

The selected plan sorts 6,303,964 rows and takes about 19.43 seconds median.

The higher-cost alternative sorts only 502 rows and takes about 2.39 seconds median.

The selected plan is approximately 8.13x slower.