Timeline for How does MySQL store the row data internally?
Current License: CC BY-SA 4.0
16 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jun 17, 2023 at 6:00 | comment | added | Rick James | @ajaysinghnegi - No assumptions about blocks, gaps, etc, are made. It will do a LogN drill-down to file id=2, ignoring that id=1 was just found. On the other hand, if you do "WHERE id >=789", it will do the drilldown to find id=789 (O(LogN)), then walk forward (O(1)) to find whatever ids are next. This is where the "+" of "B+Tree" comes into play. | |
Jun 17, 2023 at 3:31 | comment | added | asn |
Only thing to ask-suppose id is a PK and id=1,2 both reside in the same block. After the db has fetched the block containing id=1 into buf_pool, how does it know that id=2 is also in one of the buffered-blocks without again going through the indx or does it have to go through the index again to know that(which is not that expensive though)? One more thing to ask - All InnoDB indexes contain the PK column(s) in the leaves - is it possible for databases to index on a non-key attribute with leaves containing the pointer to the actual row blocks? I guess, we'll have to duplicate the data though.
|
|
Jun 17, 2023 at 3:26 | comment | added | asn | @RickJames But blocks will be cached in the "buffer_pool" only when they have been brought in there. Before that, there must be some query that asks for such blocks. So, after we get to know the PKs(from the non-key attribute via the index) which are scattered across different blocks, fetching the blocks from disk where these PKs reside is what makes the operation expensive. | |
Jun 16, 2023 at 20:44 | comment | added | Rick James | Blocks are cached in the "buffer_pool". Reading from disk is the costly part; after that the NLogN is essentially CPU time, which is rather small. | |
Jun 16, 2023 at 6:28 | comment | added | asn |
Generally, the NLogN argument is less critical than "counting the disk blocks that needed to be read". Ain't both the same? After we get the PK from the non-key attribute through a B+ tree blocks, these PKs can be present in different blocks. Yes, if many PKs reside in same blocks then the block count matters(which usually is the case).
|
|
Jun 16, 2023 at 2:24 | comment | added | Rick James | @ajaysinghnegi - All InnoDB indexes contain the PK column(s) in the leaves -- in order to reach into data's B+Tree [if needed] to get the rest of the columns. So, yes, there is a NLogN lookup for other columns. (This leads to a strong argument against using UUIDs for the PK!) Generally, the NLogN argument is less critical than "counting the disk blocks that needed to be read". (Rule of Thumb: each index or data block contains 100 index or data rows.) | |
Jun 14, 2023 at 23:47 | comment | added | asn | Slightly Off-topic: When index is used on a non-key attribute(assuming it contains duplicates) then, is a B+ tree created with on that non-key attribute with the leaf nodes containing the Primary Key column(s) too? If yes, then would the next search on that primary key be an O(Nlog(total records)) operation where N is number of records that match the query condition. Nlog(total records) bcz these N records can have vastly different primary keys and log(total rec) time for each search. Am I right? | |
Feb 25, 2020 at 5:32 | comment | added | Rick James | @user3198603 - If you want to drill down some narrower topic, start a new Question. This one is threatening to get out of hand. | |
Feb 25, 2020 at 5:28 | comment | added | Rick James | @user3198603 - Correct. See what I added. | |
Feb 25, 2020 at 5:27 | history | edited | Rick James | CC BY-SA 4.0 |
added 743 characters in body
|
Feb 25, 2020 at 1:09 | comment | added | user3198603 | Thanks. One related point is even If i have to update one specific field of row/column, first I have to read complete block containing that row and write back the complete content to that block. Right ? | |
Feb 25, 2020 at 1:06 | vote | accept | user3198603 | ||
Feb 24, 2020 at 19:21 | history | edited | Rick James | CC BY-SA 4.0 |
added 166 characters in body
|
Feb 24, 2020 at 19:19 | comment | added | Rick James | @user3198603 - Correct. A 16KB block will contain data for only one table. (More specifically for either data or secondary index for that table.) Disk allocation is a bunch of compromises... 16KB is bigger than the OS "block" size; tiny tables "waste" a lot of space; tables are segregated; indexes are segregated; some blocks are prematurely allocated; blocks are not (in general) released back to the OS; etc. | |
Feb 24, 2020 at 9:23 | comment | added | user3198603 | Rick my basic question is how data is stored for a table . I believe block reserved for a table will store data only for that table not for other table. Is that right ? | |
Feb 23, 2020 at 4:14 | history | answered | Rick James | CC BY-SA 4.0 |