MySQL 5.7 - B-Tree indexes, performance and fragmentation I have a large table with a timestamp column and it holds a very large amount of data (a few million rows).

Whenever running a filtered query by range on the timestamp column for this table, depending on the size of the range, it takes a considerable amount of time (2+ seconds). This column has an index created for it which would lead me to believe that the query return should be faster.

I noticed that by destroying the index and re-adding it, the query performs easily 40% better. 

Bellow is a simple example of how the table is structured:

create table foo (
  id int(11) not null auto_increment,
  fk_id int(11) not null,
  datecolumn timestamp,
  primary key (id, fk_id),
  key idx_timestamp (datecolumn)
  constraint fk_fk_id foreign key (fk_id) references bla (id)
 ) engine = InnoDB;


Any reason why the re-creation of the index would make the query run faster and how can I make this as part of a maintenance ? I understand that MySQL InnoDB default index is BTree and it can get messy but it should have a way to optimize or re-organize these so the query performance is not so bad.

Note: I have ran 

optimize table foo;
flush tables;


And these didn't seem to solve anything related to the index.

When you use explain it shows some indexes being used but mainly, it shows the type ranged and under this type that there is most of number of rows analyzed to return just a few of them.

fk_id is part of the where clause, needs to be, it is also part of a composite key which means that it is deterministic to return the results.

The query is basically this:

select id, fk_id, datecolumn, bar.id, bar.name, bar.type
    from foo
    join bar on bar.id = foo.fk_id
   where foo.datecolumn between '2016-01-01 05:00:00' and '2017-01-01 04:59:59'
   and foo.fk_id in (1, 2, 4)


Even if the query was a simple select where datecolumn between range I get the same result.
BTree blocks inherently go from 100% full (actually about 15/16) to about 69% full after a lot of random INSERTs.  This may account for the 40% you are seeing.  But note, it won't get any slower over time.  Hence, I see frequent OPTIMIZE TABLE as a waste of time, especially if you need the table to be accessible all the time.

And, your 40% faster will rapidly degrade.

I would expect FLUSH TABLES to actually hurt -- since it will remove cached info from RAM.

In order to discuss the query, please show us the query, its EXPLAIN SELECT ..., and perhaps SHOW CREATE TABLE bla.

foo is essentially two tables, one ordered (id, fk_id, datecolumn), the other ordered (datecolumn, id, fk_id).  Plus, I think, a secondary index of (fk_id, id) (no datecolumn).

If fk_id is part of the WHERE clause, none of them may be optimal.

Addenda

(From OP's comment:)

select  id, fk_id, datecolumn, bar.id, bar.name, bar.type
    from  foo
    join  bar  ON bar.id = foo.fk_id
    where  foo.datecolumn between '2016-01-01 05:00:00'
                              AND '2017-01-01 04:59:59'
      and  foo.fk_id in (1, 2, 4)


The optimal indexes are

foo:  INDEX(fk_id, datecolumn) -- 3 disjoint ranges
bar:  PRIMARY KEY(id) -- I assume it is already the PK; if not, then INDEX(id)


Note that you do not currently have the optimal index for foo.  Add it, and your need for OPTIMIZE TABLE should diminish.

As for why the optimize seemed to help -- probably caching.  How much RAM do you have?  What is the value of innodb_buffer_pool_size?

I prefer this pattern:

    where  foo.datecolumn between '2016-01-01 05:00:00'
                              AND '2016-01-01 05:00:00' + INTERVAL 1 YEAR


(No hassles with leap years, datatypes, etc)

More on indexing.