Default join_cache_level=2 misses ORDER BY LIMIT early-stop plan; range-checked plan does 8800 full scans

Summary

I found a reproducible optimizer performance issue on MariaDB 12.3.2.

For an ORDER BY ... LIMIT 1 join query, the optimizer chooses a low-cost default plan with the default join_cache_level=2. This setting allows flat/incremental BNL block-based join algorithms. The selected plan scans t3 first and then uses range-checked-for-each-record on t1.

However, ANALYZE FORMAT=JSON shows that range-checked-for-each-record falls back to full table scan for every outer row: 8800 full scans and zero range accesses. The query takes about 58.8 seconds.

A hinted JOIN_ORDER(t1,t3) plan is estimated as more expensive, but takes about 11.7 seconds.

More importantly, setting join_cache_level=0 exposes a much faster ORDER BY ... LIMIT early-stop plan. That plan sorts t3, then probes t1 using ref access with a rowid_filter, and stops after enough rows are found. It takes only about 7-9 ms for LIMIT 1 and LIMIT 10.

So the issue appears to be a cost-model / plan-selection problem around join cache, range-checked-for-each-record, and ORDER BY ... LIMIT row-goal optimization.

Attachment

orderby_limit_join_cache_costing.sql

How to reproduce

mysql < orderby_limit_join_cache_costing.sql > output.txt 2>&1

The testcase creates and analyzes the tables, then runs EXPLAIN FORMAT=JSON and ANALYZE FORMAT=JSON for the default query and alternative plans.

Query

The default query is:

SELECT t3.c6 AS ref0

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

WHERE t1.c1 IS NOT NULL

ORDER BY t3.c4 ASC, t3.c5 DESC

LIMIT 1;

The hinted query used for diagnosis is:

SELECT /*+ JOIN_ORDER(t1, t3) */ t3.c6 AS ref0

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

WHERE t1.c1 IS NOT NULL

ORDER BY t3.c4 ASC, t3.c5 DESC

LIMIT 1;

Data size after ANALYZE TABLE

The testcase uses a small but amplified dataset:

t1 rows:                                    17100

t1 rows where c1 IS NOT NULL:                5700

t3 rows:                                     8800

join output cardinality before ORDER/LIMIT: 10032000

Statistics are collected before running the queries:

ANALYZE TABLE t2, t3, t0, t1;

ANALYZE TABLE t2 PERSISTENT FOR ALL;

ANALYZE TABLE t3 PERSISTENT FOR ALL;

ANALYZE TABLE t0 PERSISTENT FOR ALL;

ANALYZE TABLE t1 PERSISTENT FOR ALL;

Relevant settings

The issue reproduces with these settings:

optimizer_prune_level = 0

optimizer_join_limit_pref_ratio = 0

optimizer_use_condition_selectivity = 4

use_stat_tables = PREFERABLY

join_cache_level = 2

join_buffer_size = 262144

sort_buffer_size = 2097152

not_null_range_scan = off

index_condition_pushdown = on

rowid_filter = on

join_cache_level=2 is the documented default value. It allows BNL-style block-based join algorithms. join_cache_level=0 is only used later as diagnostic evidence to show that a much faster non-block-based ORDER BY LIMIT early-stop plan exists.

Result equivalence

The default query and the hinted query return the same result:

BASE:   low_ndv_3_6_3

HINTED: low_ndv_3_6_3

Case 1: default plan with join_cache_level=2

With join_cache_level=2 and not_null_range_scan=off, the optimizer chooses the following lower-cost plan:

Estimated cost: 4679.906231

Runtime:        58761.71878 ms

Plan shape:

t3 full table scan

  -> t1 range-checked-for-each-record

  -> filesort for ORDER BY t3.c4, t3.c5 DESC LIMIT 1

Relevant EXPLAIN FORMAT=JSON excerpt:

{

  "query_block": {

    "select_id": 1,

    "cost": 4679.906231,

    "filesort": {

      "sort_key": "t3.c4, t3.c5 desc",

      "temporary_table": {

        "nested_loop": [

          {

            "table": {

              "table_name": "t3",

              "access_type": "ALL",

              "rows": 8800,

              "cost": 1.5273156

            }

          },

          {

            "range-checked-for-each-record": {

              "keys": ["i2", "i3"],

              "table": {

                "table_name": "t1",

                "access_type": "ALL",

                "key": "i3",

                "used_key_parts": ["c1"],

                "loops": 8800,

                "rows": 17100,

                "cost": 4678.378916,

                "filtered": 6.666666508

              }

            }

          }

        ]

      }

    }

  }

}

Case 1 ANALYZE result

The important part from ANALYZE FORMAT=JSON is that range-checked-for-each-record never uses range access. It falls back to full scan for every outer row:

"range-checked-for-each-record": {

  "keys": ["i2", "i3"],

  "r_keys": {

    "full_scan": 8800,

    "index_merge": 0,

    "range": {

      "i2": 0,

      "i3": 0

    }

  },

  "table": {

    "table_name": "t1",

    "access_type": "ALL",

    "loops": 8800,

    "r_loops": 8800,

    "rows": 17100,

    "r_rows": 17100,

    "cost": 4678.378916,

    "r_table_time_ms": 39436.19518,

    "r_other_time_ms": 17592.88793,

    "r_engine_stats": {

      "pages_accessed": 723378

    },

    "r_total_filtered": 6.666666667,

    "r_filtered": 6.666666667

  }

}

So the selected plan performs 8800 full scans of t1 and zero range accesses, although this plan is estimated as cheaper.

Case 2: diagnostic JOIN_ORDER plan

The hinted JOIN_ORDER(t1,t3) plan has higher estimated cost, but is much faster under join_cache_level=2:

Estimated cost: 11588.86411

Runtime:        11714.82816 ms

Plan shape:

t1 range scan on i3(c1), using index_condition "t1.c1 is not null"

  -> t3 block nested loop join

  -> filesort for ORDER BY t3.c4, t3.c5 DESC LIMIT 1

Relevant EXPLAIN FORMAT=JSON excerpt:

{

  "query_block": {

    "select_id": 1,

    "cost": 11588.86411,

    "filesort": {

      "sort_key": "t3.c4, t3.c5 desc",

      "temporary_table": {

        "nested_loop": [

          {

            "table": {

              "table_name": "t1",

              "access_type": "range",

              "key": "i3",

              "used_key_parts": ["c1"],

              "rows": 5700,

              "cost": 2.8802156,

              "index_condition": "t1.c1 is not null"

            }

          },

          {

            "block-nl-join": {

              "table": {

                "table_name": "t3",

                "access_type": "ALL",

                "rows": 8800,

                "cost": 4660.032812,

                "filtered": 20

              },

              "buffer_type": "flat",

              "buffer_size": "105KiB",

              "join_type": "BNL",

              "attached_condition": "t3.c0 = t1.c0"

            }

          }

        ]

      }

    }

  }

}

This hinted plan is only used as a diagnostic comparison. It is not the best plan found in the testcase.

Case 3: not_null_range_scan=on avoids the worst repeated full scans

I also tested:

SET SESSION optimizer_switch='not_null_range_scan=on,index_condition_pushdown=on';

With not_null_range_scan=on, the default plan changes from range-checked-for-each-record to BNL and avoids the worst repeated full-scan behavior:

Estimated cost: 4586.887401

Runtime:        12204.60187 ms

Plan shape:

t3 full table scan

  -> t1 ALL + BNL

  -> filesort for ORDER BY t3.c4, t3.c5 DESC LIMIT 1

This improves runtime from about 58.8 seconds to about 12.2 seconds, but it still does not find the much faster ORDER BY LIMIT early-stop plan.

Case 4: join_cache_level=0 exposes a fast non-block-based ORDER BY LIMIT early-stop plan

I also tested the same default query with:

SET SESSION join_cache_level = 0;

SET SESSION optimizer_switch='not_null_range_scan=off,index_condition_pushdown=on';

join_cache_level=0 disables the block-based join algorithms controlled by join_cache_level. I use it here only as diagnostic evidence, not as a general workaround recommendation.

With join_cache_level=0, the default query no longer uses range-checked-for-each-record. It uses a sorted t3 scan followed by ref access into t1 using i2(c0), with a rowid_filter on i3(c1).

LIMIT 1:

  Estimated cost: 14847.96583

  Runtime:        7.338679928 ms

Plan shape:

read_sorted_file on t3 ordered by t3.c4, t3.c5 DESC

  -> t1 ref lookup using i2(c0)

     with rowid_filter using i3(c1)

  -> stop after LIMIT is satisfied

Important ANALYZE FORMAT=JSON details:

read_sorted_file.r_rows: 1

t3 filesort.r_output_rows: 8800

t1 access_type: ref

t1 key: i2(c0)

t1 rowid_filter key: i3(c1)

t1.r_index_rows: 1

t1.r_rows: 1

Relevant excerpt:

"read_sorted_file": {

  "r_rows": 1,

  "filesort": {

    "sort_key": "t3.c4, t3.c5 desc",

    "r_output_rows": 8800,

    "table": {

      "table_name": "t3",

      "access_type": "ALL",

      "r_rows": 8800

    }

  }

},

"table": {

  "table_name": "t1",

  "access_type": "ref",

  "key": "i2",

  "used_key_parts": ["c0"],

  "rowid_filter": {

    "range": {

      "key": "i3",

      "used_key_parts": ["c1"]

    },

    "rows": 5700

  },

  "r_index_rows": 1,

  "r_rows": 1,

  "attached_condition": "t1.c1 is not null"

}

This plan can exploit ORDER BY ... LIMIT 1 by reading sorted t3 rows and stopping after the first matching joined row.

Case 5: LIMIT 10 is also fast with join_cache_level=0

To check whether the fast join_cache_level=0 plan only works because LIMIT 1 happens to find a match immediately, I also tested LIMIT 10.

LIMIT 10 with join_cache_level=0:

  Estimated cost: 14847.96583

  Runtime:        8.467069394 ms

Important ANALYZE FORMAT=JSON details:

read_sorted_file.r_rows: 1

t1.r_index_rows: 28

t1.r_rows: 10

rowid_filter.r_lookups: 28

So the fast early-stop behavior is not just a LIMIT 1 timing accident. In this dataset, the first sorted t3 row can already produce enough joined rows for LIMIT 10.

Cost/runtime mismatch

The selected default plan with join_cache_level=2 is estimated as much cheaper than the join_cache_level=0 early-stop plan, but is thousands of times slower:

Default plan with join_cache_level=2:

  cost:    4679.906231

  runtime: 58761.71878 ms

Non-block-based early-stop plan exposed with join_cache_level=0, LIMIT 1:

  cost:    14847.96583

  runtime: 7.338679928 ms

Non-block-based early-stop plan exposed with join_cache_level=0, LIMIT 10:

  cost:    14847.96583

  runtime: 8.467069394 ms

The diagnostic JOIN_ORDER(t1,t3) plan also shows a cost/runtime inversion:

Default join_cache_level=2 plan:

  cost:    4679.906231

  runtime: 58761.71878 ms

JOIN_ORDER(t1,t3) diagnostic plan:

  cost:    11588.86411

  runtime: 11714.82816 ms

Parameter sensitivity

• The issue reproduces with the default not_null_range_scan=off and join_cache_level=2. According to the documented meaning of join_cache_level, value 2 allows flat/incremental BNL block-based join algorithms and is the default.
• With not_null_range_scan=on, the default plan changes from range-checked-for-each-record to t3 ALL -> t1 ALL + BNL, and runtime improves from about 58.8 seconds to about 12.2 seconds. This avoids the worst repeated full-scan behavior, but it still does not find the much faster ORDER BY ... LIMIT early-stop plan.
• With join_cache_level=0, the block-based join algorithms controlled by join_cache_level are disabled. Under this setting, the default query uses a much faster non-block-based ORDER BY ... LIMIT early-stop plan and runs in about 7-9 ms. This is used here as diagnostic evidence, not as a general recommendation to disable join cache.
• Setting optimizer_join_limit_pref_ratio=0 is enough to reproduce the issue. The bad plan does not require a non-default join-limit preference.
• The issue does not look like a simple join-order pruning problem. The testcase uses optimizer_prune_level=0, and the alternative plans are visible under different settings/hints.
• The main problem seems to be costing/selection among the default join_cache_level=2 range-checked/block-based alternatives and the non-block-based ORDER BY ... LIMIT early-stop alternative exposed with join_cache_level=0.

Expected behavior

The optimizer should not prefer the default join_cache_level=2 t3-first range-checked-for-each-record plan if it will fall back to repeated full scans.

The cost model should account for the fallback-to-full-scan cost more accurately.

The optimizer should also consider, or at least not severely mis-rank, the much faster non-block-based ORDER BY ... LIMIT early-stop plan that sorts t3 and probes t1 using ref access with a rowid_filter. In this testcase, that plan is exposed when join_cache_level=0 and runs in about 7-9 ms, while the selected default join_cache_level=2 plan takes about 58.8 seconds.

Actual behavior

The optimizer chooses the lower-cost default plan using range-checked-for-each-record.

ANALYZE FORMAT=JSON shows 8800 full scans of t1 and zero range accesses. The query takes about 58.8 seconds.

A higher-cost diagnostic JOIN_ORDER(t1,t3) plan returns the same result and takes about 11.7 seconds.

Setting join_cache_level=0 disables the block-based join algorithms controlled by join_cache_level and exposes a much faster default plan that takes about 7-9 ms for LIMIT 1 and LIMIT 10. This is diagnostic evidence that the default join_cache_level=2 plan is severely mis-ranked; it is not meant as a general recommendation to disable join cache.