I was arguing with a coworker if SELECT * WHERE t BETWEEN ? AND ? on a MyIsam table where t is an index is significantly slower for huge tables. The hypothetically returned dataset is always the same, but in one query makes up for .1% of the tables content, and for the other... say 90%.

The table we were speaking about is used for logging. This means the index for the time t is increased chronologically, which makes analyzing the table unneccessary.

My explanation was that other then searching the index to find the first and the last row (aka the first and the last reference to the data) the performance should be the same. It would take a bit longer to search a long index compared to a small one - but returning the data should take the same time. Is this right or am I completely off the track on this one?


  • The time needed to return data depends on how much data is going to be sent, with constant bandwidth it will take longer to transfer 30 MBs than 30 KBs – Purefan Apr 23 '15 at 15:28
  • the question was asked regarding the total size of the table, not the size of the returned data. the size of the returned data would be the same - the size of the table we are querying would not. – Flo Win Apr 23 '15 at 15:32

Broadly speaking, on a MyISAM Table with a range scan, the process is:

  • Find the first Index result using the BTREE (inside the .MYI file) and access the row result (on the .MYD file) - Handler_read_key
  • Get the next result, using the index (and in the same order), until the value retrieved is larger than the one defined (multiple instances of Handler_read_next)

You can actually get this plan by observing that you get a range join type on EXPLAIN and on the Handler_* counters on SHOW SESSION STATUS.

Theoretically, the first step is O(log n) -where n is the number of records indexed (the table size)- while the second is O(m)- where m is the number of records returned. So, theoretically, a larger table will take more to return the records. Why so I say theorically? Because the O() notation can be deceitful if you do not have into account the constants. Indexes usually end up in memory, while rows (specially on MyISAM, which has not a dedicated buffer for data) can be on disk, so the difference in performance of both operations is large. Also, MyISAM has problems with large tables, so then number of levels tend not to be too large.

Let me show you an unrelated graph: Full table scan

In the above graph, the full table scan (blue line) should be flat, because all rows are examined, but it is not mainly because at that point, reading and returning 16M rows is more costly than returning only 1.

So the answer is- both operations take time, which one dominates depend on the actual value of m and n, plus the state of the database in terms of speed of hardware (memory, disk) and the state of the buffers (filesystem, key buffer). In conventional usage, an index scan of a single row is a very fast operation, but it depends comparing to what, and if you have into account extreme cases, like large tables where the BTREE index doesn't fit into memory.

  • the graph shows that the more data i want to read from the table, the better a full table scan gets and the worse a index search gets. The graph does not say anything about the size of the whole table, right? I am currently running a benchmark for vaying m and n (like you called them). – Flo Win Apr 24 '15 at 8:46

A different approach to the question/answer: What is cached when you run the query?

If what you "need" is cached in RAM, there is essentially no difference is speed. You "need"

  • m "rows" from the index; these will be blocked and consecutive (as @jynus discusses).
  • m rows of data. Because the rows were inserted essentially in t order, they will also be 'clustered'. This clustering implies that many (100?) rows will fit in each block read from disk.

Total disk hits (if nothing cached): 2m/100.

The table size indirectly could impact what is cached; this could be where your coworker is coming from.

  • A "small" table may soon be (after a few queries) fully cached in RAM.
  • A "huge" table, where you are querying on a variety of BETWEEN times, may be so big that each SELECT is hitting stuff that is not cached, hence has to read from the disk.

Reading from disk is (Rule of Thumb) 10 times as slow.

Since your question fixes the number of rows returned,

  • The bandwidth to the client is not relevant;
  • The number of blocks in the index and in the data is roughly the same (between large and small tables);
  • So, caching becomes the pivotal factor.

Even the question of the choice of query plan (as so nicely illustrated in @jynus graph) is mostly irrelevant...

  • A big table will use the index -- Scan through a tiny percentage of the index; bounce over the data for the rows. Blocks needed: 2m/100.
  • A tiny table will do a table scan -- Scan through all the table. It will waste some time on rows that are not needed, but sort of balances with not having to touch the index. Blocks needed: somewhere between m/100 and maybe 5m/100.

All of this feeds into my mantra: "Count the disk hits" -- as a way of judging performance.

(PS: Most of this discussion applies to InnoDB if INDEX(t) is a secondary index and if the PRIMARY KEY is approximately in chronological order.)

  • The issue is, he is using MyISAM, not InnoDB. I also said that the graph was unrelated, I wanted to show that depending of the constants (unit access speed) the answer will be very different- as you suggest. – jynus Apr 25 '15 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.