Skip to main content
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