#
# MDEV-34720: Poor plan choice for large JOIN with ORDER BY and small LIMIT
#
create table t1 (
a int,
b int,
c int,
col1 int,
col2 int,
index(a),
index(b),
index(col1)
);
insert into t1 select
mod(seq, 100),
mod(seq, 95),
seq,
seq,
seq
from
seq_1_to_10000;
create table t10 (
a int,
a_value char(10),
key(a)
);
insert into t10 select seq, seq from seq_1_to_100;
create table t11 (
b int,
b_value char(10),
key(b)
);
insert into t11 select seq, seq from seq_1_to_150;
set @tmp_os=@@optimizer_trace;
set optimizer_trace=1;
#
# Query 1 - basic example.
#
# Table t1 is not the first, have to use temporary+filesort:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	a	NULL	NULL	NULL	100	Using where; Using temporary; Using filesort
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set optimizer_join_limit_pref_ratio=10;
# t1 is first, key=col1 produces ordering, no filesort or temporary:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	index	a,b	col1	5	NULL	10	Using where
1	SIMPLE	t10	ref	a	a	5	test.t1.a	1	
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set @trace=(select trace from information_schema.optimizer_trace);
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
[
    {
        "limit_fraction": 0.001,
        "test_if_skip_sort_order_early": 
        [
            {
                "reconsidering_access_paths_for_index_ordering": 
                {
                    "clause": "ORDER BY",
                    "table": "t1",
                    "rows_estimation": 10000,
                    "filesort_cost": "REPLACED",
                    "read_cost": "REPLACED",
                    "filesort_type": "priority_queue with row lookup",
                    "fanout": 1,
                    "possible_keys": 
                    [
                        {
                            "index": "a",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "b",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "col1",
                            "can_resolve_order": true,
                            "direction": 1,
                            "rows_to_examine": 10,
                            "range_scan": false,
                            "scan_cost": "REPLACED",
                            "chosen": true
                        }
                    ]
                }
            }
        ],
        "can_skip_filesort": true,
        "full_join_cost": "REPLACED",
        "risk_ratio": 10,
        "shortcut_join_cost": "REPLACED",
        "shortcut_cost_with_risk": 0.495218616,
        "use_shortcut_cost": true
    }
]
#
# Query 2 - same as above but without a suitable index.
#
# Table t1 is not the first, have to use temporary+filesort:
set optimizer_join_limit_pref_ratio=0;
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col2
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	a	NULL	NULL	NULL	100	Using where; Using temporary; Using filesort
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
# t1 is first but there's no suitable index,
#   so we use filesort but using temporary:
set optimizer_join_limit_pref_ratio=10;
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col2
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	ALL	a,b	NULL	NULL	NULL	10000	Using where; Using filesort
1	SIMPLE	t10	ref	a	a	5	test.t1.a	1	
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set @trace=(select trace from information_schema.optimizer_trace);
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
[
    {
        "limit_fraction": 0.001,
        "test_if_skip_sort_order_early": 
        [],
        "can_skip_filesort": false,
        "full_join_cost": "REPLACED",
        "risk_ratio": 10,
        "shortcut_join_cost": "REPLACED",
        "shortcut_cost_with_risk": 16.2273863,
        "use_shortcut_cost": true
    }
]
#
# Query 3: Counter example with large limit
#
# Table t1 is not the first, have to use temporary+filesort:
set optimizer_join_limit_pref_ratio=0;
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 5000;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	a	NULL	NULL	NULL	100	Using where; Using temporary; Using filesort
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
# Same plan as above:
# Table t1 is not the first, have to use temporary+filesort:
set optimizer_join_limit_pref_ratio=10;
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 5000;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	a	NULL	NULL	NULL	100	Using where; Using temporary; Using filesort
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set @trace=(select trace from information_schema.optimizer_trace);
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
[
    {
        "limit_fraction": 0.5,
        "test_if_skip_sort_order_early": 
        [
            {
                "reconsidering_access_paths_for_index_ordering": 
                {
                    "clause": "ORDER BY",
                    "table": "t1",
                    "rows_estimation": 10000,
                    "filesort_cost": "REPLACED",
                    "read_cost": "REPLACED",
                    "filesort_type": "merge_sort with addon fields",
                    "fanout": 1,
                    "possible_keys": 
                    [
                        {
                            "index": "a",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "b",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "col1",
                            "can_resolve_order": true,
                            "direction": 1,
                            "rows_to_examine": 5000,
                            "range_scan": false,
                            "scan_cost": "REPLACED",
                            "usable": false,
                            "cause": "cost"
                        }
                    ]
                }
            }
        ],
        "can_skip_filesort": false,
        "full_join_cost": "REPLACED",
        "risk_ratio": 10,
        "shortcut_join_cost": "REPLACED",
        "shortcut_cost_with_risk": 197.826608,
        "use_shortcut_cost": false
    }
]
#
# Query 4: LEFT JOIN makes it impossible to put ORDER-BY-table first,
#          however the optimizer still puts it as sort_by_table.
#
set optimizer_join_limit_pref_ratio=10;
explain
select
*
from
t10 left join (t1 join t11 on t1.b=t11.b ) on t1.a=t10.a
order by
t1.col2
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	NULL	NULL	NULL	NULL	100	Using temporary; Using filesort
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set @trace=(select trace from information_schema.optimizer_trace);
# This will show nothing as limit shortcut code figures that
#   it's not possible to use t1 to construct shortcuts:
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
NULL
#
# Query 5: Same as Q1 but also with a semi-join
#
set optimizer_join_limit_pref_ratio=default;
# Table t1 is not the first, have to use temporary+filesort:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
where
t1.a in (select a from t10) and
t1.b in (select b from t11)
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	t10	index	a	a	5	NULL	100	Using where; Using index; LooseScan; Using temporary; Using filesort
1	PRIMARY	t10	ref	a	a	5	test.t10.a	1	
1	PRIMARY	t1	ref	a,b	a	5	test.t10.a	100	Using where
1	PRIMARY	t11	ref	b	b	5	test.t1.b	1	
1	PRIMARY	t11	ref	b	b	5	test.t1.b	1	Using index; FirstMatch(t11)
set optimizer_join_limit_pref_ratio=10;
# t1 is first, key=col1 produces ordering, no filesort or temporary:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
where
t1.a in (select a from t10) and
t1.b in (select b from t11)
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	t1	index	a,b	col1	5	NULL	10	Using where
1	PRIMARY	t10	ref	a	a	5	test.t1.a	1	
1	PRIMARY	t11	ref	b	b	5	test.t1.b	1	
1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	
1	PRIMARY	<subquery3>	eq_ref	distinct_key	distinct_key	4	func	1	
2	MATERIALIZED	t10	index	a	a	5	NULL	100	Using index
3	MATERIALIZED	t11	index	b	b	5	NULL	150	Using index
set @trace=(select trace from information_schema.optimizer_trace);
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
[
    {
        "limit_fraction": 0.001,
        "test_if_skip_sort_order_early": 
        [
            {
                "reconsidering_access_paths_for_index_ordering": 
                {
                    "clause": "ORDER BY",
                    "table": "t1",
                    "rows_estimation": 10000,
                    "filesort_cost": "REPLACED",
                    "read_cost": "REPLACED",
                    "filesort_type": "priority_queue with row lookup",
                    "fanout": 1,
                    "possible_keys": 
                    [
                        {
                            "index": "a",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "b",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "col1",
                            "can_resolve_order": true,
                            "direction": 1,
                            "rows_to_examine": 10,
                            "range_scan": false,
                            "scan_cost": "REPLACED",
                            "chosen": true
                        }
                    ]
                }
            }
        ],
        "can_skip_filesort": true,
        "full_join_cost": "REPLACED",
        "risk_ratio": 10,
        "shortcut_join_cost": "REPLACED",
        "shortcut_cost_with_risk": 0.535649162,
        "use_shortcut_cost": true
    }
]
#
# Query 6: same as Query 1 but let's limit the search depth
#
set @tmp_osd=@@optimizer_search_depth;
set optimizer_search_depth=1;
set optimizer_join_limit_pref_ratio=default;
# Table t1 is not the first, have to use temporary+filesort:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t10	ALL	a	NULL	NULL	NULL	100	Using where; Using temporary; Using filesort
1	SIMPLE	t11	ALL	b	NULL	NULL	NULL	150	Using join buffer (flat, BNL join)
1	SIMPLE	t1	ref	a,b	a	5	test.t10.a	100	Using where
set optimizer_join_limit_pref_ratio=10;
# t1 is first, key=col1 produces ordering, no filesort or temporary:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	index	a,b	col1	5	NULL	10	Using where
1	SIMPLE	t10	ref	a	a	5	test.t1.a	1	
1	SIMPLE	t11	ref	b	b	5	test.t1.b	1	
set @trace=(select trace from information_schema.optimizer_trace);
select json_detailed(json_extract(@trace, '$**.join_limit_shortcut_choice')) as JS;
JS
[
    {
        "limit_fraction": 0.001,
        "test_if_skip_sort_order_early": 
        [
            {
                "reconsidering_access_paths_for_index_ordering": 
                {
                    "clause": "ORDER BY",
                    "table": "t1",
                    "rows_estimation": 10000,
                    "filesort_cost": "REPLACED",
                    "read_cost": "REPLACED",
                    "filesort_type": "priority_queue with row lookup",
                    "fanout": 1,
                    "possible_keys": 
                    [
                        {
                            "index": "a",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "b",
                            "can_resolve_order": false,
                            "cause": "not usable index for the query"
                        },
                        {
                            "index": "col1",
                            "can_resolve_order": true,
                            "direction": 1,
                            "rows_to_examine": 10,
                            "range_scan": false,
                            "scan_cost": "REPLACED",
                            "chosen": true
                        }
                    ]
                }
            }
        ],
        "can_skip_filesort": true,
        "full_join_cost": "REPLACED",
        "risk_ratio": 10,
        "shortcut_join_cost": "REPLACED",
        "shortcut_cost_with_risk": 0.495218616,
        "use_shortcut_cost": true
    }
]
set optimizer_search_depth=@tmp_osd;
set optimizer_trace=@tmp_os;
# An extra testcase for MDEV-35164 (its main testcase is below).
alter table t1 add unique key(col2);
insert into t10 select * from t10;
insert into t10 select * from t10;
analyze table t10;
Table	Op	Msg_type	Msg_text
test.t10	analyze	status	Engine-independent statistics collected
test.t10	analyze	status	OK
# This will not crash and also show that sorting is not done when
#   ORDER BY only refers to const table columns:
explain
select
*
from
t1
join t10 on t1.a=t10.a
join t11 on t1.b=t11.b
where
t1.col2=3
order by
t1.col1
limit 10;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	const	col2,a,b	col2	5	const	1	
1	SIMPLE	t11	ref	b	b	5	const	1	
1	SIMPLE	t10	ref	a	a	5	const	2	
drop table t1, t10, t11;
set optimizer_join_limit_pref_ratio=default;
#
# MDEV-35072: Assertion failure with optimizer_join_limit_pref_ratio and 1-table select
#
SET optimizer_join_limit_pref_ratio=1;
CREATE TABLE t1 (c1 INT, INDEX(c1));
INSERT INTO t1  VALUES (1),(2);
SELECT * FROM t1  ORDER BY c1 LIMIT 1;
c1
1
DROP TABLE t1;
#
# MDEV-35164: optimizer_join_limit_pref_ratio: assertion when the ORDER BY table becomes constant
# Original testcase:
#
SET optimizer_join_limit_pref_ratio=1;
CREATE TABLE t1 (a INT KEY,b INT, KEY(b)) ;
INSERT INTO t1 VALUES (2,NULL);
INSERT INTO t1 VALUES (5,NULL);
SELECT * FROM t1 NATURAL JOIN t1 AS t2 WHERE t1.b=NULL ORDER BY t1.a LIMIT 1;
a	b
DROP TABLE t1;
set optimizer_join_limit_pref_ratio=default;
#
# MDEV-35072: Assertion failure with optimizer_join_limit_pref_ratio and 1-table select
#
SET optimizer_join_limit_pref_ratio=1;
CREATE TABLE t1 (c1 INT, INDEX(c1));
INSERT INTO t1  VALUES (1),(2);
SELECT * FROM t1  ORDER BY c1 LIMIT 1;
c1
1
DROP TABLE t1;
set optimizer_join_limit_pref_ratio=default;