so i was reading about database pages and DBMS in mysql and it got me really confused

so based on their documentation database pages have a part where it points to rows in the page, which have tuples of the database, but how does the DBMS find the correct page when i type something like SELECT name from mytable where id>1? there is no info on this

I Suppose the DBMS looks for the corresponding .frm, but how does it find the correct pages that should read inside that?

i read this article : https://ieeexplore.ieee.org/document/5474822/

which showed the header content of .frm files, but there was nothing in the header that helps find the correct page, then how does the DBMS find it?!

  • This is a very wide question, are you mostly interested on the internals of InnoDB or the SQL layer (query execution)- from query to "get row with ID=2". Also note that since MySQL 8.0, .frm files have stopped existing, and an internal, innodb-stored data dictionary is used. Data dictionary only stores metadata (e.g. structure of a table) but not the data itself. – jynus Nov 25 '18 at 14:03
  • @jynus yes I'm asking about InnoDB, so what does the DBMS do when i type a query like select name from mytable where x>y step by step? there is no documentation regarding this, i just want to understand how can the DBMS find the tuples? – John P Nov 25 '18 at 14:08
  • I am not sure this is suitable for a proper succinct answer- but you can read about that here: forums.mysql.com/read.php?22,577068,577068 – jynus Nov 25 '18 at 14:19
  • @jynus i have actually read some of those, the problem with InnoDB guides is that they focus on InnoDB and not the DBMS, they just tell us how InnoDB stores files and such but not how DBMS work with them – John P Nov 25 '18 at 14:37
  • I answered your more concrete questions at dba.stackexchange.com/a/223380/30545 – jynus Nov 25 '18 at 15:49

The .frm file contains nothing more than the schema. It is looked at when opening the file, then info is kept in RAM.

ibdata1 or the .ibd file is the "tablespace" for the data. It contains meta info about the data, indexes, etc. In particular, it points to the root nodes for the indexes of the table. (Note: The data is stored based on the PRIMARY KEY, so the "data" acts very much like an "index".)

From the "root" node of a B+Tree, you can drill down to an individual row.

From an individual row, it is possible (when doing a range/index/table scan) to easily find the next/previous row in the B+Tree.

The BTrees are organized in 16KB "blocks", pointed to by a tuple that contains (approximately): tablespace number and block number. Since a tablespace is a file, the block number is easily translated into a byte offset in that file. The OS has an extra layer of looking up such a logical address to find a physical address.

Within the Block, there may be, say, 100 "records" that are either data rows or index rows or links down the BTree to other blocks ("nodes"). (The "100" is a Rule of Thumb; in reality, it could be as few as 1, to as many as several thousand.)

To find a particular row (other than the "next" or "previous") within a block, some form of search is done. (I don't know whether this is a linear scan or a binary search.)

SELECT name from mytable where id>1
  1. Parse the command.
  2. "Open" the table -- either cached (cf table_open_cache) or use .frm (or Data Dictionary in MySQL 8.0)
  3. Figure out how to perform the query
  4. Find index on id. Let's say it is PRIMARY KEY(id)
  5. Locate root of B+Tree for the PK
  6. Drill down until locating the last (or, since a PK is unique, the only) row with id=1, then start at the 'next' record.
  7. Scan forward, fetching name from each row until you hit the end of the table.
| improve this answer | |
  • > I don't know whether this is a linear scan or a binary search. I was wrong, rows are not kept in order withing a page, pages are. blog.jcole.us/2013/01/10/btree-index-structures-in-innodb – jynus Nov 26 '18 at 12:33
  • @jynus - JCole's link seems to imply a forward linked list. – Rick James Nov 26 '18 at 15:10
  • Yes, I meant not physically ordered. – jynus Nov 26 '18 at 19:04

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.