-- MariaDB testcase: join-order cost ranking inversion caused by equality-join fanout misestimation
--
--
-- Symptom:
--   A plain 3-table INNER JOIN has two result-equivalent nested-loop plans.
--   The optimizer chooses t1 -> t3 -> t0. This scans about 1M rows from t1
--   and performs about 1M index lookups into t3, almost all of which miss.
--
--   The forced t3 -> t0 -> t1 plan returns the same 12 rows, but is much faster:
--   it scans about 20k rows from t3, probes t0, reduces the intermediate result
--   to 6 rows, and probes t1 only 6 times.
--
-- Important properties:
--   * Plain INNER JOIN only: no ORDER BY, LIMIT, DISTINCT, GROUP BY, subquery, or outer join.
--   * Final result is non-empty: expected 12 rows.
--   * optimizer_prune_level=0 is used to reduce the chance this is just heuristic pruning.
--   * join_cache_level=0 is used in the main comparison to avoid BKA/MRR masking the join-order issue.
--   * The testcase collects MariaDB persistent engine-independent statistics and repeats the test.
--   * On MariaDB 12.3.2, persistent statistics do not fix the plan or estimates.
--
-- Suggested command:
--   mariadb --table < mariadb_join_order_fanout_misestimation_testcase.sql > mariadb_join_order_fanout_misestimation_result.txt
--
-- Expected on MariaDB 12.3.2-like builds:
--   BASE        t1 -> t3 -> t0, around 1.0s on the reporter's machine
--   FORCED_FAST t3 -> t0 -> t1, around 30-40ms on the reporter's machine
--   Persistent statistics do not change the selected BASE join order.

DROP DATABASE IF EXISTS mariadb_join_order_fanout_misestimation;
CREATE DATABASE mariadb_join_order_fanout_misestimation;
USE mariadb_join_order_fanout_misestimation;

SELECT 'PARAMETER SNAPSHOT BEFORE SETUP' AS section;
SELECT VERSION() AS mariadb_version,
       @@optimizer_prune_level AS optimizer_prune_level_before,
       @@optimizer_search_depth AS optimizer_search_depth_before,
       @@join_cache_level AS join_cache_level_before,
       @@use_stat_tables AS use_stat_tables_before,
       @@histogram_size AS histogram_size_before,
       @@histogram_type AS histogram_type_before,
       @@optimizer_use_condition_selectivity AS optimizer_use_condition_selectivity_before;
SHOW VARIABLES LIKE 'optimizer_switch';

-- Main comparison knobs.
-- optimizer_prune_level=0: avoid making this look like a pruning/search-space issue.
-- join_cache_level=0: avoid BKA/MRR executor mitigation hiding the wrong join order.
-- use_stat_tables/histogram knobs are set to make persistent stats available when created below.
SET SESSION optimizer_prune_level = 0;
SET SESSION join_cache_level = 0;
SET SESSION use_stat_tables = 'PREFERABLY';
SET SESSION histogram_size = 254;
SET SESSION optimizer_use_condition_selectivity = 5;

SELECT 'PARAMETER SNAPSHOT AFTER SETUP KNOBS' AS section;
SELECT @@optimizer_prune_level AS optimizer_prune_level,
       @@optimizer_search_depth AS optimizer_search_depth,
       @@join_cache_level AS join_cache_level,
       @@use_stat_tables AS use_stat_tables,
       @@histogram_size AS histogram_size,
       @@histogram_type AS histogram_type,
       @@optimizer_use_condition_selectivity AS optimizer_use_condition_selectivity;

-- Row-count knobs. Keep @T1_ROWS much larger than @T3_ROWS.
-- If setup is too slow, reduce @T1_ROWS to 300000 and @T0_ROWS to 100000.
SET @T0_ROWS = 300000;
SET @T1_ROWS = 1000000;
SET @T3_ROWS = 20000;
SET @MAX_ROWS = GREATEST(@T0_ROWS, @T1_ROWS, @T3_ROWS);

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

CREATE TABLE t1(
  c0 BIGINT,
  c1 BIGINT,
  c2 DOUBLE
) ENGINE=InnoDB;

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

CREATE TABLE digits(d INT NOT NULL PRIMARY KEY) ENGINE=MEMORY;
INSERT INTO digits(d) VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

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

INSERT INTO seq_0_to_n(n)
SELECT
    d0.d
  + d1.d * 10
  + d2.d * 100
  + d3.d * 1000
  + d4.d * 10000
  + d5.d * 100000 AS n
FROM digits d0
CROSS JOIN digits d1
CROSS JOIN digits d2
CROSS JOIN digits d3
CROSS JOIN digits d4
CROSS JOIN digits d5
WHERE (
    d0.d
  + d1.d * 10
  + d2.d * 100
  + d3.d * 1000
  + d4.d * 10000
  + d5.d * 100000
) < @MAX_ROWS;

-- t0 bulk data:
--   300k rows; c3 has many distinct 3-byte prefixes.
--   Bulk t0.c3 values intentionally do not match bulk t3.c3.
INSERT INTO t0(c0, c1, c2, c3, c4, c5)
SELECT
  n % 8 AS c0,
  7 + (n % 1000) AS c1,
  CAST(n % 97 AS DOUBLE) AS c2,
  CONCAT(
    CHAR(65 + MOD(FLOOR(n / 676), 26)),
    CHAR(65 + MOD(FLOOR(n / 26), 26)),
    CHAR(65 + MOD(n, 26)),
    '_bulk_t0_',
    n
  ) AS c3,
  1000000000 - n AS c4,
  IF(n % 7 = 0, NULL, CAST(n AS DOUBLE)) AS c5
FROM seq_0_to_n
WHERE n < @T0_ROWS;

-- t1 bulk data:
--   1M rows with one dominant c0 value.
--   This dominant value does not match any bulk t3.c0.
INSERT INTO t1(c0, c1, c2)
SELECT
  1382471286 AS c0,
  -2013567063 AS c1,
  CAST(1519424050 + (n % 17) AS DOUBLE) AS c2
FROM seq_0_to_n
WHERE n < @T1_ROWS;

-- t3 bulk data:
--   20k rows; high-NDV c0 values that do not match the dominant t1.c0.
--   c3 is constant and does not match bulk t0.c3.
INSERT INTO t3(c0, c1, c2, c3)
SELECT
  1767542700 + n AS c0,
  -1698623085 AS c1,
  CAST(3200 + (n % 101) AS DOUBLE) AS c2,
  '0.9320971481798682' AS c3
FROM seq_0_to_n
WHERE n < @T3_ROWS;

-- Add a tiny non-empty overlap:
--   3 matching keys.
--   For each key: 1 row in t3, 2 rows in t0, 2 rows in t1.
--   Expected final rows: 3 * 1 * 2 * 2 = 12.
INSERT INTO t3(c0, c1, c2, c3) VALUES
  (9000000000, -1698623085, 3200.0, 'match_key_000'),
  (9000000001, -1698623085, 3201.0, 'match_key_001'),
  (9000000002, -1698623085, 3202.0, 'match_key_002');

INSERT INTO t1(c0, c1, c2) VALUES
  (9000000000, -2013567063, 1519424050.0),
  (9000000000, -2013567063, 1519424051.0),
  (9000000001, -2013567063, 1519424050.0),
  (9000000001, -2013567063, 1519424051.0),
  (9000000002, -2013567063, 1519424050.0),
  (9000000002, -2013567063, 1519424051.0);

INSERT INTO t0(c0, c1, c2, c3, c4, c5) VALUES
  (0, 7, 1.0, 'match_key_000', 2000000000, NULL),
  (1, 8, 1.0, 'match_key_000', 2000000001, NULL),
  (2, 9, 1.0, 'match_key_001', 2000000002, NULL),
  (3, 10, 1.0, 'match_key_001', 2000000003, NULL),
  (4, 11, 1.0, 'match_key_002', 2000000004, NULL),
  (5, 12, 1.0, 'match_key_002', 2000000005, NULL);

CREATE INDEX i0 ON t0(c0);
CREATE INDEX i1 ON t0(c0, c1);
CREATE INDEX i2 ON t1(c0);
CREATE INDEX i5 ON t3(c0);
CREATE INDEX i6 ON t3(c0, c1);
CREATE UNIQUE INDEX i7 USING BTREE ON t0(c3(3) ASC, c4 DESC, c1 ASC, c0 ASC);

ANALYZE TABLE t0, t1, t3;

SELECT 'SANITY CHECKS BEFORE PERSISTENT STATS' AS section;
SELECT 'row-counts' AS check_name,
       (SELECT COUNT(*) FROM t0) AS t0_rows,
       (SELECT COUNT(*) FROM t1) AS t1_rows,
       (SELECT COUNT(*) FROM t3) AS t3_rows;

SELECT 'ndv-check' AS check_name,
       (SELECT COUNT(DISTINCT LEFT(c3, 3)) FROM t0) AS t0_c3_prefix_ndv,
       (SELECT COUNT(DISTINCT c0) FROM t1) AS t1_c0_ndv,
       (SELECT COUNT(DISTINCT c0) FROM t3) AS t3_c0_ndv,
       (SELECT COUNT(DISTINCT c3) FROM t3) AS t3_c3_ndv;

SELECT 'join-counts' AS check_name,
       (SELECT COUNT(*) FROM t1 INNER JOIN t3 ON t1.c0 = t3.c0) AS t1_t3_matches,
       (SELECT COUNT(*) FROM t3 INNER JOIN t0 ON t3.c3 = t0.c3) AS t3_t0_matches,
       (SELECT COUNT(*)
        FROM t3
        INNER JOIN t0 ON t3.c3 = t0.c3
        INNER JOIN t1 ON t3.c0 = t1.c0
        WHERE t3.c1 >= -2066281069) AS final_result_rows;

-- ==============================
-- Before persistent statistics
-- ==============================

SELECT 'BASE EXPLAIN FORMAT=JSON BEFORE PERSISTENT STATS' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_FAST EXPLAIN FORMAT=JSON BEFORE PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_SLOW EXPLAIN FORMAT=JSON BEFORE PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;

SELECT 'BASE ANALYZE FORMAT=JSON BEFORE PERSISTENT STATS' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_FAST ANALYZE FORMAT=JSON BEFORE PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_SLOW ANALYZE FORMAT=JSON BEFORE PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;

-- Direct timing: do not wrap in a derived table, to avoid rewrite noise.
-- The query prints only 12 rows.
SELECT 'BASE DIRECT TIMING BEFORE PERSISTENT STATS' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS base_elapsed_ms_before_persistent_stats;

SELECT 'FORCED_FAST DIRECT TIMING BEFORE PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS forced_fast_elapsed_ms_before_persistent_stats;

SELECT 'FORCED_SLOW DIRECT TIMING BEFORE PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS forced_slow_elapsed_ms_before_persistent_stats;

-- ==============================
-- Persistent engine-independent statistics
-- ==============================

SELECT 'CREATE MARIADB PERSISTENT ENGINE-INDEPENDENT STATS' AS section;
ANALYZE TABLE t0, t1, t3 PERSISTENT FOR ALL;

SELECT 'SANITY CHECKS AFTER PERSISTENT STATS' AS section;
SELECT 'row-counts' AS check_name,
       (SELECT COUNT(*) FROM t0) AS t0_rows,
       (SELECT COUNT(*) FROM t1) AS t1_rows,
       (SELECT COUNT(*) FROM t3) AS t3_rows;

SELECT 'join-counts' AS check_name,
       (SELECT COUNT(*) FROM t1 INNER JOIN t3 ON t1.c0 = t3.c0) AS t1_t3_matches,
       (SELECT COUNT(*) FROM t3 INNER JOIN t0 ON t3.c3 = t0.c3) AS t3_t0_matches,
       (SELECT COUNT(*)
        FROM t3
        INNER JOIN t0 ON t3.c3 = t0.c3
        INNER JOIN t1 ON t3.c0 = t1.c0
        WHERE t3.c1 >= -2066281069) AS final_result_rows;

SELECT 'BASE EXPLAIN FORMAT=JSON AFTER PERSISTENT STATS' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_FAST EXPLAIN FORMAT=JSON AFTER PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_SLOW EXPLAIN FORMAT=JSON AFTER PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
EXPLAIN FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;

SELECT 'BASE ANALYZE FORMAT=JSON AFTER PERSISTENT STATS' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_FAST ANALYZE FORMAT=JSON AFTER PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;

SELECT 'FORCED_SLOW ANALYZE FORMAT=JSON AFTER PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
ANALYZE FORMAT=JSON
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;

SELECT 'BASE DIRECT TIMING AFTER PERSISTENT STATS' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
INNER JOIN t0 ON t3.c3 = t0.c3
INNER JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS base_elapsed_ms_after_persistent_stats;

SELECT 'FORCED_FAST DIRECT TIMING AFTER PERSISTENT STATS: STRAIGHT_JOIN t3,t0,t1' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t3
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
STRAIGHT_JOIN t1 ON t3.c0 = t1.c0
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS forced_fast_elapsed_ms_after_persistent_stats;

SELECT 'FORCED_SLOW DIRECT TIMING AFTER PERSISTENT STATS: STRAIGHT_JOIN t1,t3,t0' AS section;
SET @start = CURRENT_TIMESTAMP(6);
SELECT t0.c4 AS ref0, t0.c3 AS ref1
FROM t1
STRAIGHT_JOIN t3 ON t3.c0 = t1.c0
STRAIGHT_JOIN t0 ON t3.c3 = t0.c3
WHERE t3.c1 >= -2066281069;
SELECT TIMESTAMPDIFF(MICROSECOND, @start, CURRENT_TIMESTAMP(6)) / 1000.0
       AS forced_slow_elapsed_ms_after_persistent_stats;

SELECT 'FINAL NOTES' AS section;
SELECT 'Interpretation guide' AS note,
       'If BASE remains t1->t3->t0 and is close to FORCED_SLOW while much slower than FORCED_FAST, this demonstrates a join-order cost ranking inversion caused by equality-join fanout misestimation. If persistent stats do not change the plan/estimate, classify it as fanout misestimation despite MariaDB persistent engine-independent statistics.' AS details;
