Why MySQL SELECT performance depends on table size?
Eventually I realized that it was some king of caching and probably on Linux level. 

After applying # sync &amp;&amp; echo 3 | tee /proc/sys/vm/drop_caches followed by mysql&gt; RESET QUERY CACHE; the query time became linear. 

Note though, that before this the effect was stable on different queries.