-- ============================================================================
-- MariaDB optimizer reproducer
--
-- Title:
--   LIMIT-aware join-order costing applies a shortcut cost to a BNL plan
--   that still performs a full join and join-result filesort
--
-- Target version:
--   MariaDB 12.3.2
--
-- Summary:
--   With optimizer_join_limit_pref_ratio enabled, the optimizer assigns a
--   LIMIT-shortcut-adjusted cost to a plan whose final physical execution
--   still uses Block Nested Loop (BNL), materializes the complete join result,
--   and performs filesort.
--
--   The shortcut cost assumes that rows can be produced in ORDER BY order and
--   execution can stop after LIMIT rows. However, the selected BNL access path
--   uses join buffering and the final plan still contains a join-result
--   filesort, so the join cannot stop early.
--
-- Expected:
--   A LIMIT shortcut cost should only be used for a physical plan that
--   preserves the required ordering and can stop after producing LIMIT rows.
--   A final BNL + join-result-filesort plan should retain its full execution
--   cost, or the optimizer should choose a non-buffered order-preserving plan.
--
-- Actual:
--   For the query below, optimizer_join_limit_pref_ratio=10 or 100 causes the
--   displayed plan cost to be reduced dramatically, while the final plan
--   remains BNL + temporary table + filesort and executes the complete join.
--
-- Suggested execution:
--
--   mariadb --table \
--     < mariadb_order_limit_bnl_cost_reproducer.sql \
--     > mariadb_order_limit_bnl_cost_reproducer.out 2>&1
--
-- ANALYZE FORMAT=JSON executes the query. Each important runtime comparison is
-- repeated three times.
-- ============================================================================

DROP DATABASE IF EXISTS mariadb_order_limit_bnl_cost_repro;
CREATE DATABASE mariadb_order_limit_bnl_cost_repro
  CHARACTER SET utf8mb4;
USE mariadb_order_limit_bnl_cost_repro;

-- Preserve the caller's session settings.
SET @saved_join_cache_level := @@SESSION.join_cache_level;
SET @saved_optimizer_join_limit_pref_ratio :=
    @@SESSION.optimizer_join_limit_pref_ratio;
SET @saved_optimizer_trace := @@SESSION.optimizer_trace;
SET @saved_optimizer_trace_max_mem_size :=
    @@SESSION.optimizer_trace_max_mem_size;
SET @saved_max_statement_time := @@SESSION.max_statement_time;

SET SESSION max_statement_time = 20;
SET SESSION optimizer_trace_max_mem_size = 33554432;

SELECT
    VERSION() AS server_version,
    DATABASE() AS database_name,
    @@SESSION.join_cache_level AS initial_join_cache_level,
    @@SESSION.optimizer_join_limit_pref_ratio
        AS initial_optimizer_join_limit_pref_ratio,
    @@SESSION.join_buffer_size AS join_buffer_size;

-- ============================================================================
-- 1. Deterministic data set
-- ============================================================================

CREATE TABLE digits (
    d TINYINT UNSIGNED NOT NULL PRIMARY KEY
) ENGINE=InnoDB;

INSERT INTO digits(d)
VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

CREATE TABLE seq_0_999 (
    n INT UNSIGNED NOT NULL PRIMARY KEY
) ENGINE=InnoDB;

INSERT INTO seq_0_999(n)
SELECT
    d0.d
  + d1.d * 10
  + d2.d * 100
FROM digits AS d0
CROSS JOIN digits AS d1
CROSS JOIN digits AS d2;

-- The outer table is naturally readable in k order through idx_k.
CREATE TABLE t_outer (
    id INT UNSIGNED NOT NULL PRIMARY KEY,
    k INT NOT NULL,
    payload INT NOT NULL,
    pad CHAR(80) NOT NULL,
    KEY idx_k (k)
) ENGINE=InnoDB;

-- The inner table has the same four join keys, but rows are physically inserted
-- in interleaved key order: 1,2,3,4,1,2,3,4,...
--
-- idx_k makes a ref access path available, while the wider selected row makes
-- the BNL scan attractive in the normal full-cost comparison.
CREATE TABLE t_inner (
    id INT UNSIGNED NOT NULL PRIMARY KEY,
    k INT NOT NULL,
    payload INT NOT NULL,
    pad CHAR(120) NOT NULL,
    KEY idx_k (k)
) ENGINE=InnoDB;

INSERT INTO t_outer(id, k, payload, pad)
SELECT
    n + 1,
    FLOOR(n / 32) + 1,
    11,
    RPAD('o', 80, 'o')
FROM seq_0_999
WHERE n < 128;

INSERT INTO t_inner(id, k, payload, pad)
SELECT
    n + 1,
    MOD(n, 4) + 1,
    7,
    RPAD('i', 120, 'i')
FROM seq_0_999
WHERE n < 192;

ANALYZE TABLE t_outer, t_inner;

SHOW CREATE TABLE t_outer;
SHOW CREATE TABLE t_inner;
SHOW INDEX FROM t_outer;
SHOW INDEX FROM t_inner;

SELECT
    (SELECT COUNT(*) FROM t_outer) AS outer_rows,
    (SELECT COUNT(*) FROM t_inner) AS inner_rows,
    (SELECT COUNT(DISTINCT k) FROM t_outer) AS outer_key_ndv,
    (SELECT COUNT(DISTINCT k) FROM t_inner) AS inner_key_ndv,
    (
      SELECT COUNT(*)
      FROM t_outer AS o
      INNER JOIN t_inner AS i ON i.k = o.k
    ) AS joined_rows;

SELECT k, COUNT(*) AS outer_rows_per_key
FROM t_outer
GROUP BY k
ORDER BY k;

SELECT k, COUNT(*) AS inner_rows_per_key
FROM t_inner
GROUP BY k
ORDER BY k;

SELECT id, k
FROM t_inner
ORDER BY id
LIMIT 16;

-- Common query used by all main tests:
--
-- 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;

-- ============================================================================
-- 2. Baseline: LIMIT-aware join-order preference disabled
-- ============================================================================

SET SESSION join_cache_level = 2;
SET SESSION optimizer_join_limit_pref_ratio = 0;

SELECT 'BASELINE: join_cache_level=2, ratio=0' AS test_case;

EXPLAIN FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

-- Expected plan characteristics:
--   block-nl-join
--   temporary_table
--   filesort
--   full outer and inner input consumption

-- ============================================================================
-- 3. Suspected bug: ratio=10
-- ============================================================================

SET SESSION join_cache_level = 2;
SET SESSION optimizer_join_limit_pref_ratio = 10;

SELECT 'SUSPECTED BUG: join_cache_level=2, ratio=10' AS test_case;

EXPLAIN FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

-- On the affected build, the final plan remains BNL + filesort, but the
-- top-level cost is reduced from approximately 2.3602 to approximately 0.0293.

-- ============================================================================
-- 4. Optimizer trace for the affected query
-- ============================================================================

SET SESSION join_cache_level = 2;
SET SESSION optimizer_join_limit_pref_ratio = 10;
SET SESSION optimizer_trace = 'enabled=on';

SELECT 'TRACE: join_cache_level=2, ratio=10' AS test_case;

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;

SELECT
    QUERY,
    TRACE,
    MISSING_BYTES_BEYOND_MAX_MEM_SIZE,
    INSUFFICIENT_PRIVILEGES
FROM information_schema.OPTIMIZER_TRACE;

SET SESSION optimizer_trace = 'enabled=off';

-- Important trace fields on the affected build:
--
--   access_type: "scan_with_join_cache"
--   uses_join_buffering: true
--   can_skip_filesort: true
--   full_join_cost: approximately 2.3602
--   shortcut_join_cost: approximately 0.00293
--   risk_ratio: 10
--   shortcut_cost_with_risk: approximately 0.0293
--   use_shortcut_cost: true
--
-- The contradiction is that the shortcut search retains a join-buffered access
-- path, but still concludes that the final join can skip filesort and stop
-- after LIMIT rows.

-- ============================================================================
-- 5. Same physical plan shape with ratio=100
-- ============================================================================

SET SESSION join_cache_level = 2;
SET SESSION optimizer_join_limit_pref_ratio = 100;

SELECT 'SUSPECTED BUG: join_cache_level=2, ratio=100' AS test_case;

EXPLAIN FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

-- On the affected build, the final plan is still BNL + filesort and performs
-- the same work, while the top-level cost becomes approximately 0.2933.

-- ============================================================================
-- 6. Exact shortcut/full-cost crossover
-- ============================================================================

-- The observed shortcut cost is approximately 0.002932635.
--
--   0.002932635 * 804 = 2.357838...
--   0.002932635 * 805 = 2.360770...
--
-- The full BNL plan cost is approximately 2.360202.
-- Therefore ratio=804 should still use the shortcut cost, while ratio=805
-- should reject it and restore the full cost.

SET SESSION join_cache_level = 2;

SET SESSION optimizer_join_limit_pref_ratio = 804;

SELECT 'CROSSOVER: ratio=804' AS test_case;

EXPLAIN FORMAT=JSON
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;

SET SESSION optimizer_join_limit_pref_ratio = 805;

SELECT 'CROSSOVER: ratio=805' AS test_case;

EXPLAIN FORMAT=JSON
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;

-- ============================================================================
-- 7. Control: disable join buffering
-- ============================================================================

-- This keeps the same table order but removes BNL. The resulting ordinary
-- nested-loop execution preserves the outer index order and can stop after
-- producing three rows.

SET SESSION join_cache_level = 0;
SET SESSION optimizer_join_limit_pref_ratio = 10;

SELECT 'CONTROL: join_cache_level=0, ratio=10' AS test_case;

EXPLAIN FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

-- Expected control characteristics:
--   no block-nl-join
--   no join-result filesort
--   outer actual rows approximately 1
--   inner actual rows approximately 9
--   execution stops after producing LIMIT rows

-- ============================================================================
-- 8. Control: force the available ref access path
-- ============================================================================

SET SESSION join_cache_level = 2;
SET SESSION optimizer_join_limit_pref_ratio = 10;

SELECT 'CONTROL: forced non-buffered ref access' AS test_case;

EXPLAIN FORMAT=JSON
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;

SHOW WARNINGS;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

ANALYZE FORMAT=JSON
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;

-- Expected control characteristics:
--   t_outer index scan
--   t_inner ref(idx_k)
--   no join-result filesort
--   outer actual rows approximately 1
--   inner actual rows approximately 3

-- ============================================================================
-- 9. Compact comparison summary
-- ============================================================================

SELECT
    'Inspect the preceding EXPLAIN/ANALYZE output for:' AS note
UNION ALL
SELECT
    'ratio=0: full BNL cost, BNL + filesort, complete join execution'
UNION ALL
SELECT
    'ratio=10/100: shortcut-adjusted cost, but the same BNL + filesort work'
UNION ALL
SELECT
    'ratio=804/805: exact switch between shortcut cost and full cost'
UNION ALL
SELECT
    'join_cache_level=0: true order-preserving early termination'
UNION ALL
SELECT
    'forced ref: true indexed early termination';

-- Restore the caller's session settings.
SET SESSION join_cache_level = @saved_join_cache_level;
SET SESSION optimizer_join_limit_pref_ratio =
    @saved_optimizer_join_limit_pref_ratio;
SET SESSION optimizer_trace = @saved_optimizer_trace;
SET SESSION optimizer_trace_max_mem_size =
    @saved_optimizer_trace_max_mem_size;
SET SESSION max_statement_time = @saved_max_statement_time;

SELECT
    'DONE' AS status,
    DATABASE() AS reproduction_database,
    @@SESSION.join_cache_level AS restored_join_cache_level,
    @@SESSION.optimizer_join_limit_pref_ratio
        AS restored_optimizer_join_limit_pref_ratio;
