Cost model chooses slower join order for GROUP BY/ORDER BY LIMIT query with highly selective predicate on joined table

Summary

MariaDB 12.3.2 chooses a slower join order for a 2-table INNER JOIN with GROUP BY / ORDER BY / LIMIT when the selective predicate is on the joined table.

The default plan has a lower estimated cost:

t0 -> t1

estimated cost: 398.6052868

actual time:    770.3745928 ms

Forcing the opposite join order has a higher estimated cost but is much faster:

JOIN_ORDER(t1,t0)

t1 -> t0

estimated cost: 533.6416582

actual time:    310.4196722 ms

The faster plan is not chosen even with optimizer_join_limit_pref_ratio=1, which is the most aggressive non-zero setting.

Relation to existing optimizer issues

This seems related to the known ORDER BY/GROUP BY LIMIT join-order costing family, especially:

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

However, this repro appears to be a remaining subcase rather than an exact duplicate.

The distinguishing point is that the faster join order is not faster because it starts from the ORDER BY table and uses a pure LIMIT shortcut. Instead, the faster join order starts from the table with an extremely selective predicate, filters 200000 rows down to 5 rows, and then performs only 5 ref lookups into the other table.

Even optimizer_join_limit_pref_ratio=1 does not change the chosen plan.

How to reproduce

Please run the attached SQL file:

mariadb --table --verbose < mariadb_join_order_selective_predicate_repro.sql > mariadb_join_order_selective_predicate_repro.out 2>&1

The SQL file creates two InnoDB tables with 200000 rows each, creates indexes, collects table statistics, and runs EXPLAIN FORMAT=JSON / ANALYZE FORMAT=JSON for both the default plan and the forced JOIN_ORDER(t1,t0) plan.

Schema shape

CREATE TABLE t0(

  c0 BIGINT,

  c1 BIGINT,

  c2 DOUBLE,

  c3 VARCHAR(64)

) ENGINE=InnoDB;

CREATE TABLE t1(

  c0 BIGINT,

  c1 BIGINT,

  c2 DOUBLE,

  c3 VARCHAR(64),

  c4 BIGINT,

  c5 DOUBLE,

  c6 VARCHAR(64)

) ENGINE=InnoDB;

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);

Query

The main query is deterministic with respect to GROUP BY:

SELECT t0.c0, MIN(t0.c3) AS min_c3, MIN(t0.c1) AS min_c1

FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0

WHERE (t1.c6 = '') OR (t1.c1 = 0)

GROUP BY t0.c0

ORDER BY t0.c0 DESC

LIMIT 5;

Forced plan:

SELECT /*+ JOIN_ORDER(t1,t0) */ t0.c0, MIN(t0.c3) AS min_c3, MIN(t0.c1) AS min_c1

FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0

WHERE (t1.c6 = '') OR (t1.c1 = 0)

GROUP BY t0.c0

ORDER BY t0.c0 DESC

LIMIT 5;

Data distribution

Both tables have 200000 rows and high NDV on c0:

t0 rows: 200000, NDV(c0): 200000

t1 rows: 200000, NDV(c0): 200000

The t1 predicate is extremely selective:

WHERE (t1.c6 = '') OR (t1.c1 = 0)

matching t1 rows: 5 / 200000

matching c0 values: 1000, 1001, 1002, 1003, 1004

The expected result has 5 groups:

c0

----

1004

1003

1002

1001

1000

Observed behavior with optimizer_join_limit_pref_ratio=0

Default plan:

Plan:

  t0 range(i0) -> t1 ref(i2)

Estimated cost:

  398.6052868

ANALYZE:

  r_total_time_ms: 770.3745928

  t0.r_rows:       200000

  t1.r_loops:      200000

  t1.r_filtered:   0.0025

Handler stats:

  Handler_read_key:  200000

  Handler_read_next: 200000

  Handler_read_prev: 200000

Forced JOIN_ORDER(t1,t0):

Plan:

  t1 range(i2) -> t0 ref(i0)

Estimated cost:

  533.6416582

ANALYZE:

  r_total_time_ms: 310.4196722

  t1.r_rows:       200000

  t1.r_filtered:   0.0025

  t0.r_loops:      5

Handler stats:

  Handler_read_key:  5

  Handler_read_next: 5

  Handler_read_prev: 200000

The forced plan has a higher estimated cost but runs about 2.5x faster.

Observed behavior with optimizer_join_limit_pref_ratio=1

The same behavior is observed with the most aggressive non-zero value:

SET optimizer_join_limit_pref_ratio = 1;

Default plan remains unchanged:

Plan:

  t0 range(i0) -> t1 ref(i2)

Estimated cost:

  398.6052868

ANALYZE:

  r_total_time_ms: 768.6965209

  t1.r_loops:      200000

  t1.r_filtered:   0.0025

Forced JOIN_ORDER(t1,t0) remains faster:

Plan:

  t1 range(i2) -> t0 ref(i0)

Estimated cost:

  533.6416582

ANALYZE:

  r_total_time_ms: 308.2018123

  t0.r_loops:      5

Expected behavior

The optimizer should either choose the t1 -> t0 join order, or at least estimate it as cheaper than the selected t0 -> t1 plan.

The selected default plan performs about 200000 ref lookups into t1, although the predicate on t1 only matches 5 rows. The forced plan applies the highly selective t1 predicate first and then performs only 5 ref lookups into t0.

Why this looks like a cost model / join-order issue

The main issue is not merely the runtime gap. The estimated cost ranks the plans in the wrong order:

Default plan:

  cost: 398.6052868

  actual: 770.3745928 ms

Forced JOIN_ORDER(t1,t0):

  cost: 533.6416582

  actual: 310.4196722 ms

The cost model appears to prefer starting from t0, likely because t0.c0 matches the GROUP BY / ORDER BY key. However, this misses the benefit of starting from t1, where the predicate reduces 200000 rows to 5 rows before joining to t0.

Notes

This repro intentionally uses a deterministic GROUP BY query with MIN() to avoid relying on non-aggregated selected columns outside the GROUP BY list.

The issue is reproducible with optimizer_join_limit_pref_ratio=0 and optimizer_join_limit_pref_ratio=1.