optimizer_join_limit_pref_ratio applies shortcut cost to BNL plan that still requires full join and filesort

Description

I found an inconsistency in the plan costing performed when optimizer_join_limit_pref_ratio is enabled for an ORDER BY ... LIMIT query.

For the attached testcase, the optimizer first selects a Block Nested Loop access path for the inner table:

access_type: scan_with_join_cache

uses_join_buffering: true

The complete cost of this join order is:

full_join_cost: 2.360202464

The optimizer_join_limit_pref_ratio optimization then observes that the first table can be read through an index satisfying ORDER BY o.k and reports:

can_skip_filesort: true

shortcut_join_cost: 0.002932635

risk_ratio: 10

shortcut_cost_with_risk: 0.029326347

use_shortcut_cost: true

The cost assigned to the selected join order is consequently reduced from:

2.360202464

to:

0.029326347

However, the final physical plan still contains:

block-nl-join

temporary_table

filesort

ANALYZE FORMAT=JSON confirms that the plan processes the complete join rather than stopping after producing the first three rows.

The issue appears to be that optimizer_join_limit_pref_ratio applies its shortcut cost after selecting a join-buffered BNL access path, without accounting for the fact that join buffering prevents this physical plan from preserving the ordering supplied by the first table's index scan.

The BNL plan therefore receives an early-termination cost even though its final execution still materializes and sorts the complete join result.

This incorrectly makes the BNL plan appear cheaper than genuine non-buffered plans that can stop after producing LIMIT rows.

Reproduction

The attached SQL file creates the complete database and deterministic data set.

The main query is:

SELECT o.k, i.payload

FROM t_outer AS o

INNER JOIN t_inner AS i ON i.k = o.k

ORDER BY o.k

LIMIT 3;

The data set contains:

t_outer rows:       128

t_inner rows:       192

distinct join keys: 4

joined rows:        6144

Each key occurs 32 times in t_outer and 48 times in t_inner:

4 * 32 * 48 = 6144 joined rows

The optimizer also estimates 6144 joined rows. Therefore, the issue does not appear to be caused primarily by an incorrect join-cardinality estimate.

Baseline with optimizer_join_limit_pref_ratio=0

SET join_cache_level=2;

SET optimizer_join_limit_pref_ratio=0;

EXPLAIN FORMAT=JSON reports:

cost: 2.360202464

t_outer:

  access_type: index

  key: idx_k

  rows: 128

t_inner:

  access_type: ALL

  join_type: BNL

  rows: 192

temporary_table

filesort

ANALYZE FORMAT=JSON confirms:

t_outer actual rows: 128

t_inner actual rows: 192

Three execution times:

2.320805682 ms

2.320793808 ms

2.423858294 ms

Median:

2.320805682 ms

Behavior with optimizer_join_limit_pref_ratio=10

SET join_cache_level=2;

SET optimizer_join_limit_pref_ratio=10;

The reported cost changes to:

0.029326347

This is approximately 80.5 times lower than the baseline cost:

2.360202464 / 0.029326347 = approximately 80.5

However, the final physical plan is unchanged:

t_outer index scan

t_inner full scan with BNL

temporary table

filesort

ANALYZE FORMAT=JSON still reports:

t_outer actual rows: 128

t_inner actual rows: 192

Three execution times:

2.415670207 ms

2.378117725 ms

2.339406999 ms

Median:

2.378117725 ms

Thus, enabling optimizer_join_limit_pref_ratio reduces the estimated cost by approximately 80 times, but the selected physical plan, examined rows, and execution time remain essentially unchanged.

Optimizer trace

The optimizer trace first compares the inner-table access paths:

ref access:

  index: idx_k

  rows: 48

  cost: 6.21361152

scan_with_join_cache:

  rows: 192

  rows_out: 48

  cost: 2.334780864

  cost_without_join_buffer: 5.307392

It selects:

chosen_access_method:

  type: scan

  uses_join_buffering: true

The complete join order is estimated as:

rows_for_plan: 6144

cost_for_plan: 2.360202464

The optimizer_join_limit_pref_ratio processing then reports:

limit_fraction: 0.0004882812

can_skip_filesort: true

full_join_cost: 2.360202464

risk_ratio: 10

shortcut_join_cost: 0.002932635

shortcut_cost_with_risk: 0.029326347

use_shortcut_cost: true

The selected join order consequently receives:

best_join_order: [o, i]

cost: 0.029326347

This appears internally inconsistent:

1. The selected access method for t_inner uses join buffering.
2. The final physical plan contains BNL, a temporary table, and filesort.
3. The complete join must be processed before ORDER BY ... LIMIT can be applied.
4. Nevertheless, optimizer_join_limit_pref_ratio reports can_skip_filesort=true and applies the shortcut cost.

Behavior with optimizer_join_limit_pref_ratio=100

SET join_cache_level=2;

SET optimizer_join_limit_pref_ratio=100;

The reported cost becomes:

0.293263472

The final physical plan is still the same BNL + temporary table + filesort plan.

ANALYZE FORMAT=JSON still reports:

t_outer actual rows: 128

t_inner actual rows: 192

Three execution times:

2.313014942 ms

2.313750263 ms

2.362752730 ms

Median:

2.313750263 ms

Changing the ratio from 10 to 100 changes only the shortcut-adjusted cost. It does not change the physical plan or enable early termination.

Shortcut/full-cost crossover

The trace reports:

shortcut_join_cost: 0.002932635

full_join_cost:     2.360202464

With optimizer_join_limit_pref_ratio=804:

0.002932635 * 804 = approximately 2.357838

EXPLAIN reports:

cost: 2.357838314

The physical plan is still BNL + temporary table + filesort.

With optimizer_join_limit_pref_ratio=805:

0.002932635 * 805 = approximately 2.360771

This exceeds the full join cost, so EXPLAIN returns to:

cost: 2.360202464

The physical plan remains BNL + temporary table + filesort.

This exact crossover confirms that the cost assigned to the BNL plan is derived from the optimizer_join_limit_pref_ratio shortcut formula, although the final plan cannot stop after producing LIMIT rows.

Control 1: disable join buffering

SET join_cache_level=0;

SET optimizer_join_limit_pref_ratio=10;

The table order remains:

t_outer -> t_inner

The plan no longer contains BNL, a temporary table, or filesort.

ANALYZE FORMAT=JSON reports:

t_outer actual rows: 1

t_inner actual rows: 9

The plan stops after producing three joined rows.

Three execution times:

0.015893877 ms

0.011182347 ms

0.010146505 ms

Median:

0.011182347 ms

The reported cost is:

0.04384105

This genuine early-termination plan is more than 200 times faster than the selected BNL plan, but its reported cost is higher:

BNL + filesort:       0.029326347

non-buffered NL:      0.043841050

The BNL plan wins the cost comparison because it incorrectly receives the optimizer_join_limit_pref_ratio shortcut cost.

Control 2: force the available ref access

SELECT /*+ JOIN_ORDER(o, i) NO_BNL(i) */

       o.k, i.payload

FROM t_outer AS o FORCE INDEX FOR ORDER BY (idx_k)

INNER JOIN t_inner AS i FORCE INDEX FOR JOIN (idx_k)

  ON i.k = o.k

ORDER BY o.k

LIMIT 3;

The physical plan is:

t_outer:

  access_type: index

  key: idx_k

t_inner:

  access_type: ref

  key: idx_k

no temporary table

no join-result filesort

ANALYZE FORMAT=JSON reports:

t_outer actual rows: 1

t_inner actual rows: 3

Three execution times:

0.021344381 ms

0.017156253 ms

0.016025413 ms

Median:

0.017156253 ms

Its reported cost is:

0.04826595

This genuine early-termination plan also loses the cost comparison because the BNL plan incorrectly receives the lower cost of 0.029326347.

Expected result

optimizer_join_limit_pref_ratio should only apply its shortcut cost when the selected physical plan can preserve the required ORDER BY order and stop after producing LIMIT rows.

For this query, the optimizer should either:

1. Retain the full cost for the join-buffered BNL + join-result-filesort plan; or
2. Select a non-buffered, order-preserving plan and apply the optimizer_join_limit_pref_ratio shortcut cost to that plan.

A final physical plan containing BNL followed by complete join-result materialization and filesort should not receive a cost based on LIMIT early termination.

Actual result

When optimizer_join_limit_pref_ratio is enabled, the optimizer:

1. Selects scan_with_join_cache for the inner table.
2. Records uses_join_buffering=true.
3. Checks that t_outer.idx_k can satisfy ORDER BY o.k.
4. Treats the complete join order as if it can skip filesort.
5. Applies the shortcut-adjusted cost to the complete BNL join order.
6. Selects the BNL plan because its adjusted cost is lower than the costs of genuine non-buffered alternatives.
7. Finally executes BNL + temporary table + filesort and processes the complete join.

Suspected root cause

This appears to be an interaction between optimizer_join_limit_pref_ratio costing and physical ordering-property propagation.

The optimizer correctly recognizes that t_outer.idx_k produces rows in ORDER BY o.k order.

However, this ordering property appears to remain associated with the complete join order after the inner-table access path has been selected as:

scan_with_join_cache

uses_join_buffering: true

The apparent incorrect reasoning is:

t_outer is scanned in o.k order

  -> the complete join result is considered ordered

  -> filesort is considered skippable

  -> the join is considered able to stop after LIMIT rows

  -> optimizer_join_limit_pref_ratio shortcut cost is applied

The actual execution is:

t_outer is scanned in o.k order

  -> t_inner is joined using BNL / join buffering

  -> the required result ordering is not preserved

  -> the complete join result is materialized

  -> filesort is performed

  -> LIMIT is applied only after the complete join

The issue therefore does not appear to be primarily:

• Cardinality estimation: the 6144-row join cardinality is estimated correctly.
• Plan enumeration: ref and non-buffered nested-loop alternatives can be generated.

The problem is that optimizer_join_limit_pref_ratio applies its shortcut cost to a join-buffered BNL plan that does not possess the ordering and early-termination properties assumed by that cost.

Related issues

• MDEV-34720 - Poor plan choice for large JOIN with ORDER BY and small LIMIT
• MDEV-4205 - Make join optimization take into account ORDER BY ... LIMIT
• MDEV-8306 - Complete cost-based optimization for ORDER BY with LIMIT

MDEV-4205 notes that join buffering must not be used for a plan that relies on ORDER BY ... LIMIT early termination, because join buffering breaks the required ordering.

MDEV-34720 describes applying the reduced LIMIT cost when the join output is produced in the required order, or after changing the access method so that the required order is produced.

The optimizer behavior observed in this testcase appears inconsistent with those assumptions: optimizer_join_limit_pref_ratio retains a join-buffered BNL access path and applies the shortcut cost, while the final physical plan still materializes and filesorts the complete join result.