MariaDB – Why the Query Optimizer Chooses a Bad Execution Plan

We have a mariadb table (stories) with above 1TB of data, periodically running a query that fetches recently added rows for indexing somewhere else.

innodb_version: 5.6.36-82.1
version       : 10.1.26-MariaDB-0+deb9u1

The query works just fine when the query optimizer decides on using the secondary index to do a range walk through (in buckets of a 1000)

explain extended     SELECT  stories.item_guid
    FROM  `stories`
    WHERE  (updated_at >= '2018-09-21 15:00:00')
      AND  (updated_at <= '2018-09-22 05:30:00')
    ORDER BY  `stories`.`id` ASC
    LIMIT  1000;

+------+-------------+---------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+---------------------------------------+
| id   | select_type | table   | type  | possible_keys               | key                         | key_len | ref  | rows   | filtered | Extra                                 |
+------+-------------+---------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+---------------------------------------+
|    1 | SIMPLE      | stories | range | index_stories_on_updated_at | index_stories_on_updated_at | 5       | NULL | 192912 |   100.00 | Using index condition; Using filesort |
+------+-------------+---------+-------+-----------------------------+-----------------------------+---------+------+--------+----------+---------------------------------------+
1 row in set, 1 warning (0.00 sec)

But occasionally, even with small differences in the data set (Note the second timestamp difference with the query above, worth to mention that the whole table holds data for several years and holds several dozens millions of rows) decides to use the primary key index

explain extended     SELECT  stories.item_guid
    FROM  `stories`
    WHERE  (updated_at >= '2018-09-21 15:00:00')
      AND  (updated_at <= '2018-09-22 06:30:00')
    ORDER BY  `stories`.`id` ASC
    LIMIT  1000;

+------+-------------+---------+-------+-----------------------------+---------+---------+------+--------+----------+-------------+
| id   | select_type | table   | type  | possible_keys               | key     | key_len | ref  | rows   | filtered | Extra       |
+------+-------------+---------+-------+-----------------------------+---------+---------+------+--------+----------+-------------+
|    1 | SIMPLE      | stories | index | index_stories_on_updated_at | PRIMARY | 8       | NULL | 240259 |    83.81 | Using where |
+------+-------------+---------+-------+-----------------------------+---------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

Causing it to walk through the whole primary key index (I guess sequentially) to then filter on updated_at field taking several hours to complete instead.

The query was created by the ORM ActiveRecord and is probably far from ideal, as a workaround solution we came up with a couple of manually crafted queries, that moves the ORDER BY stories.id out, and/or using use/force index to avoid the PK since we are really filtering our data set by updated_at.

What I'm interested in understanding here is how/why the query optimizer chooses that execution plan, I understand that query optimizer uses index/table statistics for taking that decision but in this case, and If my understanding is correct about how innodb works, this is pretty clear that walking through a huge PK while not using any PK id for filtering is not ideal.

I'm essentially trying to understand where that "bad" decision comes from, what statistics or unknowns variables are used not to end up with the good plan (the one that is often chosen and which is orders of magnitude faster)

feel free to correct any of my assumptions as I'm definitively not a DBA expert,

Thanks in advance!