RHEL8

I am trying on current 10.5 (10.5.11) and I see this plan:

+------+-------------+---------+-------+------------------+------------------+---------+------+--------+-----------------------+

| id   | select_type | table   | type  | possible_keys    | key              | key_len | ref  | rows   | Extra                 |

+------+-------------+---------+-------+------------------+------------------+---------+------+--------+-----------------------+

|    1 | SIMPLE      | mytable | range | mytable_col1_idx | mytable_col1_idx | 3       | NULL | 101358 | Using index condition |

+------+-------------+---------+-------+------------------+------------------+---------+------+--------+-----------------------+

I get the same on 10.5.9.

Table def

 CREATE TABLE `mytable` (

  `col1` mediumint(9) NOT NULL DEFAULT 0,

  `col2` mediumint(9) NOT NULL DEFAULT 0,

  KEY `mytable_col1_idx` (`col1`),

  KEY `mytable_ col2_idx` (`col2`)

) ENGINE=MyISAM DEFAULT CHARSET=latin1

The table in the test dataset has 1.7M rows, the query is an OR of 5661 conditions in form col1=NNN OR ....

The number of range exceeds eq_range_index_dive_limit, so the estimate of #values in one range is taken from the index statistics. Could ANALYZE TABLE help here?

Ok, I was able to reproduce.

+------+-------------+---------+------+------------------+------+---------+------+---------+-------------+

| id   | select_type | table   | type | possible_keys    | key  | key_len | ref  | rows    | Extra       |

+------+-------------+---------+------+------------------+------+---------+------+---------+-------------+

|    1 | SIMPLE      | mytable | ALL  | mytable_col1_idx | NULL | NULL    | NULL | 1761063 | Using where |

+------+-------------+---------+------+------------------+------+---------+------+---------+-------------+

Relevant portion of Optimizer trace:

    {

      "rows_estimation": [

        {

          "table": "mytable",

          "range_analysis": {

            "table_scan": {

              "rows": 1761063,

              "cost": 355226.2292

            },

            "analyzing_range_alternatives": {

              "range_scan_alternatives": [

                {

                  "index": "mytable_col1_idx",

                  "ranges": [

+--5631 lines: "(28775) <= (col1) <= (28775)",---------

                  ],

                  "rowid_ordered": false,

                  "using_mrr": false,

                  "index_only": false,

                  "rows": 416694,

                  "cost": 506571.1092,

                  "chosen": false,

                  "cause": "cost"

                }

That is, it is not picking the range access because it thinks its cost is bigger than that of full table scan.

The number of rows it expects: 416694
This gives 74 rows per each lookup key.

Index statistics:

MariaDB [test1]> show keys from mytable\G

*************************** 1. row ***************************

        Table: mytable

   Non_unique: 1

     Key_name: mytable_col1_idx

 Seq_in_index: 1

  Column_name: col1

    Collation: A

  Cardinality: 23798

     Sub_part: NULL

       Packed: NULL

         Null: 

   Index_type: BTREE

      Comment: 

Index_comment: 

The estimate of 74 rows per lookup key agrees with the real dataset.
The Cardinality in the index statistics (23798) agrees with the actual cardinality value of 23765.

However the query itself will return only 107 rows.

Suggested workaround: set eq_range_index_dive_limit to a value that's higher than the number of elements in the IN-list (5641). Or, set it it to 0, which was the default before MariaDB 10.4.2.

Note: MySQL-8 suffers from the same issue (with innodb: except when one runs the query after loading the data. After one runs ANALYZE TABLE, the bad query plan is chosen). PostgreSQL picks a good query plan, but it will switch to poor query plan if the query has more "col1=const" disjuncts.

Notes from the optimizer call:
One option we could use is to estimate a few ranges with records_in_range calls, and then extrapolate the result to all ranges.
This won't be 100% bulletproof, though (One can imagine cases where the optimizer would still pick the wrong plan).
Also, this will add quite a bit of complexity. Do we really need to add it to handle this case? Could it be that this is a niche case that's not worth it?

The cause

This bug is a consequence of eq_range_index_dive_limit optimization (let's denote it as EQ-OPT).

The goal of EQ-OPT was to speed up the query optimization (right! optimization, not execution) by using index statistics estimates (this is table-wide average, cheap to use but imprecise), instead of using so-called "records-in-range estimates" (more precise but expensive to get) for queries that scan a lot of equality ranges.

Using imprecise estimates can cause the optimizer to pick a bad query plan. It happens when the reality is far from the estimate.
Your query is an example of this. On average, a single col1=value matches 70 rows. However, the query scans "rare" values, where 5641 values produce 107 matching rows in total.

The impact

The optimizer will use bad query plans for workloads that scan the "outliers" - values that are much more or much less common than others.

The workaround

Setting the eq_range_index_dive_limit will cause the optimizer to spend more time but construct better query plans.