MySQL disk scanning algorithm [closed]

Question

How does MySQL (InnoDB engine) read data from disk? What scanning algorithm does it use? Since the rows are stored in data pages will it read the entire data page to get the resulting rows?

Answer 1

The subject is quite broad and this could (actually does) fill a full book even. If you're interested in more details I recommend reading some. I'll try to summarise the baseline.

InnoDB is using pages to store data. Normally it is 16k but is configurable on some MySQL forks (Percona for example). This is the smallest item which is read from or written to disk (except the innodb_logs but that's a different story). 64 consecutive page make an extent (1MB) and extents are grouped in segments. The tablespace contains multiple segments.

Row are stored in B+Tree structure based on the primary key. Secondary keys are also stored in B+Tree having the primary key at the end.

Primary key lookup

InnoDB is doing a tree traversal on the PRIMARY KEY and return the row.

Secondary key lookup

• either traversing the secondary key finding the primary key(s) fulfilling the requirements and then the PK traversal.
• or using the adaptive_hash_buffer to get the primary key from the conditions and then do the PK traversal (this can be quite efficient: benchmarking secondary key updates in MySQL)

In case of any read if the page is not present in the buffer pool InnoDB fetch it from the disk (and sometimes other to for read ahead) and put it in the buffer pool. It may need to evict some other to have space for it. In case of innodb_flush_neighbors it can flush more.

Then the row or rows will be fetched and returned.

I hope this gave you something to start with.

Innodb_ruby is very useful tool to look into the physical structure of ibd files. Can give you a lot of insight into the internal behaviour.

5.5 doesn't have a feature to show the contents of the buffer pool unfortunately. In Percona Server 5.5 (not in Oracle MySQL) you can dump the contents of the buffer pool, which can be a way to look what's inside.

The best book I think is High Performance MySQL, 3rd Edition

A couple of years ago I wrote a blog post about how to learn to become a DBA. That might contain some useful information for you also.