#
# 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-38072 Optimizer choosing the wrong plan
#
CREATE TABLE t0 (
actor_id bigint(20) unsigned NOT NULL AUTO_INCREMENT,
actor_name varbinary(255) NOT NULL,
PRIMARY KEY (actor_id),
UNIQUE KEY actor_name (actor_name)
) ENGINE=InnoDB DEFAULT CHARSET=binary;
CREATE TABLE t1 (
log_id int(10) unsigned NOT NULL AUTO_INCREMENT,
log_type varbinary(32) NOT NULL DEFAULT '',
log_timestamp binary(14) NOT NULL DEFAULT '19700101000000',
log_params blob NOT NULL,
log_actor bigint(20) unsigned NOT NULL,
index log_actor_type_time (log_actor,log_type,log_timestamp),
index log_type_time (log_type,log_timestamp),
index log_actor_time (log_actor,log_timestamp),
index log_times (log_timestamp),
PRIMARY KEY (log_id)
) ENGINE=InnoDB  DEFAULT CHARSET=binary;
insert into t0 select seq, seq from seq_1_to_10;
update t0 set actor_name = 'DGG' where actor_id = 4;
insert into t1
(log_timestamp, log_actor, log_params, log_type)
select
19700101+seq,
floor(seq / 400), /* log_actor, 50x */
'log-params-value=log-params-value',
concat('val-', 100 + mod(seq, 100))  /* log_type */
from
seq_1_to_20000;
analyze table t0, t1;
Table Op Msg_type Msg_text
test.t0 analyze status Engine-independent statistics collected
test.t0 analyze status OK
test.t1 analyze status Engine-independent statistics collected
test.t1 analyze Warning Engine-independent statistics are not collected for column 'log_params'
test.t1 analyze status OK
set optimizer_trace=1;
#
# Bad query plan:  t1 has access_type:index, key=log_times
#
explain format=json
SELECT log_id, log_type, log_params, log_timestamp
FROM t0, t1
WHERE
t0.actor_name = 'DGG' and
t0.actor_id = t1.log_actor and
t1.log_type NOT IN ('val-110', 'val-120', 'val-130', 'val-133', 'val-144',
'val-155', 'val-160', 'val-170', 'val-180')
ORDER BY
log_timestamp DESC, log_id DESC
LIMIT 2;
EXPLAIN
{
  "query_block": {
    "select_id": 1,
    "cost": "COST_REPLACED",
    "nested_loop": [
      {
        "table": {
          "table_name": "t0",
          "access_type": "const",
          "possible_keys": ["PRIMARY", "actor_name"],
          "key": "actor_name",
          "key_length": "257",
          "used_key_parts": ["actor_name"],
          "ref": ["const"],
          "rows": 1,
          "filtered": 100,
          "using_index": true
        }
      },
      {
        "table": {
          "table_name": "t1",
          "access_type": "range",
          "possible_keys": [
            "log_actor_type_time",
            "log_type_time",
            "log_actor_time"
          ],
          "key": "log_actor_time",
          "key_length": "8",
          "used_key_parts": ["log_actor"],
          "loops": 1,
          "rows": 400,
          "cost": "COST_REPLACED",
          "filtered": 91,
          "attached_condition": "t1.log_actor = 4 and t1.log_type not in ('val-110','val-120','val-130','val-133','val-144','val-155','val-160','val-170','val-180')"
        }
      }
    ]
  }
}
#
# Better query plan: t1 has access_type:range, key=log_actor_time, used_key_parts: log_actor
#
explain format=json
SELECT log_id, log_type, log_params, log_timestamp
FROM t0, t1
WHERE
t0.actor_name = 'DGG' and
t0.actor_id = t1.log_actor and
t1.log_type NOT IN ('val-110', 'val-120', 'val-130', 'val-133', 'val-144',
'val-155', 'val-160', 'val-170', 'val-180')
ORDER BY
log_timestamp DESC, log_id DESC
LIMIT 2;
EXPLAIN
{
  "query_block": {
    "select_id": 1,
    "cost": "COST_REPLACED",
    "nested_loop": [
      {
        "table": {
          "table_name": "t0",
          "access_type": "const",
          "possible_keys": ["PRIMARY", "actor_name"],
          "key": "actor_name",
          "key_length": "257",
          "used_key_parts": ["actor_name"],
          "ref": ["const"],
          "rows": 1,
          "filtered": 100,
          "using_index": true
        }
      },
      {
        "table": {
          "table_name": "t1",
          "access_type": "range",
          "possible_keys": [
            "log_actor_type_time",
            "log_type_time",
            "log_actor_time"
          ],
          "key": "log_actor_time",
          "key_length": "8",
          "used_key_parts": ["log_actor"],
          "loops": 1,
          "rows": 400,
          "cost": "COST_REPLACED",
          "filtered": 91,
          "attached_condition": "t1.log_actor = 4 and t1.log_type not in ('val-110','val-120','val-130','val-133','val-144','val-155','val-160','val-170','val-180')"
        }
      }
    ]
  }
}
drop table t0, t1;
SET GLOBAL innodb_stats_persistent=default;
# End of 10.11 tests
#
# 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;