-- MariaDB optimizer testcase:
-- ORDER BY LIMIT cost model misses faster join order when the leading
-- ORDER BY key is equivalent through an INNER JOIN equality.
--
-- Tested target: MariaDB 12.3.x
--
-- Phenomenon:
--   Query orders by:      t0.c0 ASC, t1.c3 DESC
--   Join condition:       t1.c0 = t0.c0
--   Therefore on joined rows, ORDER BY t0.c0,t1.c3 is equivalent to
--   ORDER BY t1.c0,t1.c3.
--
--   However, for the original ORDER BY t0.c0,t1.c3, the optimizer chooses:
--     t0 ALL scan -> t1 ref lookup -> temporary/filesort
--
--   Forcing t1 first, or rewriting the ORDER BY key to t1.c0, gives:
--     t1 sorted/index scan -> t0 ref lookup
--
--   The latter plan is costed slightly higher but is much faster in practice
--   because ORDER BY ... LIMIT can stop after probing only a few sorted outer rows.
--
-- Expected symptom on the scaled data below:
--   BASE original:
--     cost lower, runtime much slower, many t1 ref lookups
--   JOIN_ORDER(t1,t0) / STRAIGHT_JOIN:
--     cost slightly higher, runtime much faster, actual t0 ref loops very small
--   Equivalent ORDER BY t1.c0,t1.c3:
--     optimizer chooses the fast t1-first plan automatically
--
-- This is intended as a specific subcase related to ORDER BY LIMIT cost-based
-- join-order optimization, not as a join-cache/range-checked/DISTINCT/GROUP BY case.

DROP DATABASE IF EXISTS mariadb_order_limit_equality_key_costing;
CREATE DATABASE mariadb_order_limit_equality_key_costing;
USE mariadb_order_limit_equality_key_costing;

-- Make the test deterministic and avoid join-cache/BNL noise.
SET SESSION optimizer_prune_level = 0;
SET SESSION join_cache_level = 0;
SET SESSION optimizer_join_limit_pref_ratio = 0;

SELECT 'initial optimizer variables' AS section;
SELECT @@version AS version,
       @@optimizer_prune_level AS optimizer_prune_level,
       @@optimizer_join_limit_pref_ratio AS optimizer_join_limit_pref_ratio,
       @@join_cache_level AS join_cache_level,
       @@optimizer_switch AS optimizer_switch;

CREATE TABLE t0(
  c0 BIGINT,
  c1 BIGINT,
  c2 DOUBLE,
  c3 VARCHAR(64),
  c4 BIGINT
) ENGINE=InnoDB;

CREATE TABLE t1(
  c0 BIGINT,
  c1 BIGINT,
  c2 DOUBLE,
  c3 VARCHAR(64),
  c4 BIGINT,
  c5 DOUBLE
) ENGINE=InnoDB;

-- Scaled data shape:
--   4000 distinct join keys
--   t0 has 12 rows/key, t1 has 18 rows/key
--   total join rows before filtering: 4000 * 12 * 18 = 864000
--
-- This keeps the per-key fanout close to the small original testcase while
-- making the runtime gap large enough to be visible.
SET @NDV := 4000;
SET @T0_REP := 12;
SET @T1_REP := 18;

CREATE TEMPORARY TABLE d(n INT PRIMARY KEY);
INSERT INTO d VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

CREATE TEMPORARY TABLE nums AS
SELECT
  a.n
  + 10*b.n
  + 100*c.n
  + 1000*d4.n
  + 10000*e.n
  + 100000*f.n AS n
FROM d a
CROSS JOIN d b
CROSS JOIN d c
CROSS JOIN d d4
CROSS JOIN d e
CROSS JOIN d f;

ALTER TABLE nums ADD PRIMARY KEY(n);

-- t0.c0 is uniform over @NDV.
-- t0.c4 is almost always NOT NULL, so the predicate does not explain the
-- speedup by selectivity.
INSERT INTO t0(c0, c1, c2, c3, c4)
SELECT
  MOD(n, @NDV) AS c0,
  1000000 - MOD(n, @NDV) AS c1,
  (MOD(n * 1103515245 + 12345, 200000) - 100000) / 1.0 AS c2,
  CASE WHEN MOD(n, 5) = 0
       THEN CONCAT('null_heavy_0_3_', n)
       ELSE NULL
  END AS c3,
  CASE WHEN MOD(n, 200) = 0
       THEN NULL
       ELSE MOD(n * 2654435761, 200000) - 100000
  END AS c4
FROM nums
WHERE n < @NDV * @T0_REP;

-- t1.c0 uses the same key domain as t0.c0.
-- t1.c3 is used by ORDER BY, and t1.c2 is projected.
INSERT INTO t1(c0, c1, c2, c3, c4, c5)
SELECT
  MOD(n, @NDV) AS c0,
  10000 + n * 2 AS c1,
  1200.0 + ((MOD(n * 37, 1000) - 500) / 10.0) AS c2,
  CONCAT('gaussian_1_3_', LPAD(MOD(n * 97, 1000000), 6, '0')) AS c3,
  MOD(n * 48271, 200000) - 100000 AS c4,
  2000000 - n AS c5
FROM nums
WHERE n < @NDV * @T1_REP;

-- Indexes.
CREATE INDEX idx_t0_c0 ON t0(c0);
CREATE INDEX idx_t0_c0_c1 ON t0(c0, c1);
CREATE INDEX idx_t1_c0 ON t1(c0);
CREATE INDEX idx_t1_c1 ON t1(c1);

-- Covering index that enables the fast t1-first sorted-outer plan.
-- It is intentionally not (c0,c3,c2): the optimizer still uses filesort on t1,
-- but can sort/read only t1 first and then stop early during t0 ref lookups.
CREATE INDEX idx_t1_c3_c0_c2 ON t1(c3, c0, c2);

ANALYZE TABLE t0, t1;
ANALYZE TABLE t0 PERSISTENT FOR ALL;
ANALYZE TABLE t1 PERSISTENT FOR ALL;

SELECT 'data shape' AS section;
SELECT
  (SELECT COUNT(*) FROM t0) AS t0_rows,
  (SELECT COUNT(*) FROM t1) AS t1_rows,
  (SELECT COUNT(DISTINCT c0) FROM t0) AS t0_ndv,
  (SELECT COUNT(*) / COUNT(DISTINCT c0) FROM t0) AS t0_rows_per_key,
  (SELECT COUNT(DISTINCT c0) FROM t1) AS t1_ndv,
  (SELECT COUNT(*) / COUNT(DISTINCT c0) FROM t1) AS t1_rows_per_key;

SELECT 'join cardinality' AS section;
SELECT COUNT(*) AS join_rows_before_filter
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0;

SELECT COUNT(*) AS join_rows_after_filter
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL;

SHOW INDEX FROM t0;
SHOW INDEX FROM t1;

-- ============================================================
-- 1. Original query: optimizer chooses the slower lower-cost plan.
-- ============================================================

SET SESSION optimizer_prune_level = 0;
SET SESSION join_cache_level = 0;
SET SESSION optimizer_join_limit_pref_ratio = 0;

SELECT '1A BASE original: ORDER BY t0.c0, t1.c3 LIMIT 3' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

ANALYZE FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

-- ============================================================
-- 2. Forced t1-first plan: costed higher but much faster.
-- ============================================================

SELECT '2A HINTED JOIN_ORDER(t1,t0): original ORDER BY LIMIT 3' AS section;
EXPLAIN FORMAT=JSON
SELECT /*+ JOIN_ORDER(t1, t0) */ t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

ANALYZE FORMAT=JSON
SELECT /*+ JOIN_ORDER(t1, t0) */ t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

-- STRAIGHT_JOIN expresses the same forced join order without a MariaDB comment hint.
SELECT '2B STRAIGHT_JOIN t1 -> t0: original ORDER BY LIMIT 3' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 STRAIGHT_JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

ANALYZE FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 STRAIGHT_JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

-- ============================================================
-- 3. Equivalent ORDER BY rewrite:
--    t0.c0 and t1.c0 are equal on joined rows.
--    This rewrite usually makes the optimizer choose the fast plan automatically.
-- ============================================================

SELECT '3A BASE rewritten: ORDER BY t1.c0, t1.c3 LIMIT 3' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT 3;

ANALYZE FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT 3;

-- Diagnostic result comparison for the first rows.
SELECT '3B first rows, original ORDER BY' AS section;
SELECT t0.c0 AS t0_c0, t1.c0 AS t1_c0, t1.c3, t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 10;

SELECT '3C first rows, rewritten ORDER BY' AS section;
SELECT t0.c0 AS t0_c0, t1.c0 AS t1_c0, t1.c3, t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT 10;

-- ============================================================
-- 4. optimizer_join_limit_pref_ratio does not cover the original query.
--    These are EXPLAIN only to keep runtime reasonable.
-- ============================================================

SET SESSION optimizer_join_limit_pref_ratio = 1;

SELECT '4A original, optimizer_join_limit_pref_ratio=1' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

SET SESSION optimizer_join_limit_pref_ratio = 100;

SELECT '4B original, optimizer_join_limit_pref_ratio=100' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

SET SESSION optimizer_join_limit_pref_ratio = 0;

-- ============================================================
-- 5. The optimizer_switch has orderby_uses_equalities=on by default,
--    but the original query still does not get the fast plan.
-- ============================================================

SELECT '5A optimizer_switch check' AS section;
SELECT @@optimizer_switch AS optimizer_switch;

SELECT '5B original ORDER BY with orderby_uses_equalities currently enabled' AS section;
EXPLAIN FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 3;

-- ============================================================
-- 6. LIMIT sweep: the bad plan still joins/sorts almost everything,
--    while the forced plan only probes a few sorted outer rows.
-- ============================================================

SELECT '6A BASE LIMIT 300' AS section;
ANALYZE FORMAT=JSON
SELECT t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 300;

SELECT '6B HINTED LIMIT 300' AS section;
ANALYZE FORMAT=JSON
SELECT /*+ JOIN_ORDER(t1, t0) */ t1.c2 AS ref0
FROM t1 INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT 300;

SELECT 'done' AS section;
