MySQL 5.7 - B-Tree indexes, performance and fragmentation
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.