How do indexes make databases read faster?
ฝัง
- เผยแพร่เมื่อ 14 มี.ค. 2022
- System Design for SDE-2 and above: arpitbhayani.me/masterclass
System Design for Beginners: arpitbhayani.me/sys-design
Redis Internals: arpitbhayani.me/redis
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafters.io/join?via=...
In this video, I explained how indexing speeds up databases by reducing disk I/O. I delved into the basics of database structure, disk block reading, and the role of indexes. Without indexes, reading all rows sequentially can be slow, but with indexes, queries become much faster. I demonstrated how creating an index on a specific column can significantly enhance query performance. By efficiently utilizing indexes, database operations can achieve up to an 8x improvement in speed, showcasing the crucial role of indexes in optimizing database performance.
Recommended videos and playlists
If you liked this video, you will find the following videos and playlists helpful
System Design: • PostgreSQL connection ...
Designing Microservices: • Advantages of adopting...
Database Engineering: • How nested loop, hash,...
Concurrency In-depth: • How to write efficient...
Research paper dissections: • The Google File System...
Outage Dissections: • Dissecting GitHub Outa...
Hash Table Internals: • Internal Structure of ...
Bittorrent Internals: • Introduction to BitTor...
Things you will find amusing
Knowledge Base: arpitbhayani.me/knowledge-base
Bookshelf: arpitbhayani.me/bookshelf
Papershelf: arpitbhayani.me/papershelf
Other socials
I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
LinkedIn: / arpitbhayani
Twitter: / arpit_bhayani
Weekly Newsletter: arpit.substack.com
Thank you for watching and supporting! it means a ton.
I am on a mission to bring out the best engineering stories from around the world and make you all fall in
love with engineering. If you resonate with this then follow along, I always keep it no-fluff. - วิทยาศาสตร์และเทคโนโลยี
People run behind influencers and left with this GoldMine! Loved ur content.. following you when you joined Unacademy. 1 of the Most knowledgeable and inspiring person in the Tech Field.
🙌🙌 areeee thanks 🤘
indeed
Great content...what I understood before is that if you have index on certain column, db will make the record s sequential on the basis of that column and it will access the record like an element is accessed from an array in o(1). That made me doubt as well sometimes when I thought to add indexes on multiple columns.
This video made the concept crystal for me
Your videos are so simple to understand and the pace is also very easy to follow. Great work !!! Perfect for me, and you are also covering very relevant important topics. Keep up the work, man.
Wonderful explanation of such an important topic. The way you explained it with practical examples made the concept quite clear to me. Thank you so much!
wowww so simple yet so elegent.
Indices explained in the most simplest of terms. Excellent video , thank you Arpit.
Very informative video. Thanks @Arpit Sir.
Fantastic! You have a real flair for teaching mate!
This was wonderfully explained 🙏
Inspiring content. Thanks a lot sir
Best video ever on the indexing concept. Thanks, Arpit, expecting many more videos from you on system designing. By the way, your neat notes are enough to clear all doubts. It will be good if you could add a video on the time complexity of operations like updating and delete on millions of data. How to increase the performance of DB like partition, and segregation techniques. Yes, I read this on many blogs but feel like they are half explanatory so need to understand them in depth.
Thanks alot i learn alot from your content it is clear and to the point !
you nailed it !! seriously its the best explanation I have ever seen for Index thank you 🙏
Thank you, Arpit!
Thanks bro!! Loved the content... great one!!
Really liked how you explain things so easily with that much detail, totally awesome arpit sir 😁
Thanks for this video Arpit. I asked an EM about indexing, as it was only a buzzword to me at that point, couldn't wrap my head around jargons back then. I was able to relate this video as to how I used to search for words in my Oxford dictionary from the index written on the first few pages. Thanks for making super imaginable.
Great video. I just want to tell you that you have a typo on your thumbnail image - "indices" instead of indexes.
This is just too good! Thanks man.
Thank you for lesson.. its awesome..
The content and explanation is just too awesome
Beautiful explanation brother!
Nice and clear explanation 👍
Superb explanation!!
Great explanation!
Really superb explanation, you not nailed normally but nailed it deeply 🙌
Many people have superficial knowledge about indexing. All they know is that indexing makes querying faster. But they don’t know how. Glad I found this video through your twitter post. Will read about B+ trees soon.
21:49 perfect example of a range query optimization.
Recently discovered your channel, very engaging content! Thanks
Arpit bhaiya trust me this was really awesome (though I knew about indexes but still learnt many new things), Thanx ^_^
I am lucky that I stumbled upon your channel it's really asli engineering in the true sense
I really appreciate such content which touches the foundation concepts
Thank you again, Asli me asli engineering 🙏🙏🙏
Bro You probably in google 1cr package. Because you have a huse knowledge abouts system. I watch your almost 20+ video and every video has nice and details information. So you do amazing work, to teach Deep concept about engineering side.
👍👍👍
Waiting for your book on System Design one day. There is real need for such book in the market. Keep inspiring.
I don't think even my professor in under grad or grad school has taught me like they way you're explaining the concepts so succinctly, thank you.
Hello, Arpit.
It would be fantastic if you could include the following two points in the video or answer them here.
1. Can we index on the string (varchar/text), and if so, what happens?
2. What are the drawbacks of indexing (will it take up more memory?) Where should we not do it?
Thanks for a great video! It helped me gain understanding of how an index works on a table while querying. It would be great if you could also make a video on how indexes are stored eg. B+ tree and what happens behind the scenes when a query with indexed column is fired.
Loved the way you simplified the concept. Would you recommend any book(s) for the concepts includes Indexing, Cursor, Query Optimization etc?
Brilliant Video Arpit :) , Thank you so much, clears alot of concepts around Indexes :)
Thanks man!
Thanks brother for this video it helped me alot very nice explanation subscribed you
Amazing content 🙌
Wow aaj pata chala 😂 literally Gold 🔥🔥🔥🔥 keep it up sir
Maza aa gaya! Behtareen! 🔥
Great content sir! 😄
Just a summary:
Whenever a record is read from the DB, the entire block is fetched which contains that particular record. Since block reads are expensive(takes more time to read) it is better to index the records based on the property you want to search. So now when you search the record it is first checked into the index table which is stored in quite a few blocks, so block read time will be very low. Since we know in which of the blocks, the exact record(which can be computed from index table using id attribute) is present, we can directly compute those blocks and return the record from them.
To the point 😁
Hey Arpit - When db engine have to read multiple blocks, is that operation sequential or multi-threaded? Sequential can be too slow right? This is regarding example for reading 34 blocks taking 34 seconds...
for alter table scripts when we add columns..does block allocation gets redone ?
Brilliant Video :)
I think it's bit a wrong
1) when we find the age in physical table that time process not read all table like name, age, bio and totalblogs, read only things age. This means read by default 2 block mean 2 second.
2) In above case they created non clustered index without primary key ( clustered index ) this means, in disk data stored in inserted order and create by default RID.
And when create non clustered index on age that time it's map sorting age and RID of the record,
Now when we use search age==23 than process go through B-tree (binary tree - root and index node make decisions and go to leaf node and give the RID - leaf node contain group of RID or clustered index ) that create on age (non clustered index) and process go through it's like binary search and find equivalent RID. Now we have group of RID actual pointer address now we go through physical address and retire data.
You made index content as so simple 🤪. Great explanation 🎉
thanks bruh!
Hi bro. Can you please tell me. Is index take more ram when compared without index?
Good explaination , btw what tool are you using in your explanation @Arpit
How will this work for lets say a string value or a text area
Also in the worst case, it may happen that the age =23 records are present across all the 34 blocks, in that case the performance with indexing will even be poor I think: 2+34 =36
This guy is good!
Please make a video on types of index (sparse and dense) and real life use case
Great Video, Arpit !!
It'd be interesting if you could make a video on BTree Indexes and clustered BTree Indexes.
Soon :)
Till Arpit makes one you can check out this video. th-cam.com/video/aZjYr87r1b8/w-d-xo.html
Hi Arpit,
Really thanks for creating such wonderful content and including how disk space getting managed for database.
Curious to know what happens the blocks, when we add new column or change datatypes of column. Because in that case overall row size will change, and if data is stored in disk sequential order, then how databases internally manage that size change. If we consider a row which was earlier of size 200Byte and then later converted to 900Byte or so, I assume majority of the block reference which clustered index was holding will also change. That looks like huge write operation. Curious to know how that gets managed internally??
Would love an answer on below query:
If there are 34 records with age 23 in the entire db of 100 users and worst case spread across all 34 blocks; wouldn't indexing use more time - 2s for index + 34s for fetching 34 records from 34 block?
Very good explanation on index, learnt a ton !! Thanks
One doubt, what if the resultant IDs from the index were part of each of the 37 blocks ?
Eg: IDs - 1,4,7,10,13,16,.....
Then we would read all 37 blocks so totally
37 sec + 2 sec( reading index ) > sequential read
So when should we not use an index on a column ?
can u pls help here @AsliEngineering
Key points to take:
1. While reading the data it reads full blocks
2. Making an indices will create the separate table like structure with sorted order along with its primary key mapped
How do we know that the 4th index is in the second block only?
we used index for integer column so index fit in 2 blocks, if we have used string as index column (60 or 128 bytes), index would have been much larger, and hence take many blocks , right ? (60 + 4) * 100 = 6400 = 11 blocks
Hi Arpit,
Amazing explanation. Thanks.
I wa wondering how this block size (600B in your case) is decided?
Typical size if 4kb. I took 600 as an example. Not too small not too large is the only criteria
does this mean that dbms creates an index for the column when a query is run on that column? i understood how indexing works. i just dont understand at what point an index table for each of the columns in a db is created.
You are required to create indexes on columns that you will be querying. You typically do this while creating the table, or after that by firing CREATE INDEX query.
after getting row id, how does the DB engine know which row to fetch exactly (assuming its not a PK or even if its a PK, in both cases, if it makes a diff) & from which block on disk?
have a members-only video on that already.
Question: What if one of the fetched index is 1000, now fetch the data block where this row is present a sequencial scan till that data block happens or is there some other way?
Ahh, with a little researching I got to know that index also holds the "rowId" which is not the primary key but the internal id to identify which diskstore the row data might be present. This make sense to me but what confirmation if that is indeed the case.
Hi Arpit,
I didn't understand the part after we get the IDs after applying indexes. How will it search the IDs (buffered from the indexing) in the non-indexed database?
in the example you provided while calculating query time after indexing, the two IDs you searched for were 7 and 2. And in your example, 7th ID occured in the first block while the 2nd ID was in the second block. What if the 2nd ID was in the 4th block? Would the database search in every memory block i.e. 2nd and 3rd and then 4th until it gets the 2nd ID?
Read about B+ trees and how they work. That will help you understand how rows are fetched.
How do we know or guarantee ( based on id column in this example) that our table is stored sequentially ( 17:37 ) which helped us to read first two blocks ? I am assuming id column marked as PK. You can correct me please
I think the assumption is table stored in B+ tree structure.
Do you have any suggestions on how to optimize writes/updates if there's an index column? You can assume you aren't updating index column value, but there are millions of rows to update.
If the updates does not change the values on the index column there will not be any write happening on the index. This evaluation is taken care by the query optimization stage.
In general when a massive update is run, there is a possibility of table (if not rows) are locked in order to protect and give a consistent view of the data to transaction happening at that moment.
One way to ensure your DB performance is not hampered much because of massive update is by breaking it into micro transaction if possible. This way the db will be locking a few rows at a time.
Let me know if you have any other special use-case which I did not cover. Happy to answer.
Can you share an example for the question being asked please.
12:51 great content 😁
Hey Arpit, amazing explanation !!! I had a doubt that is it safe to assume that no matter what the Query is(considering only select queries with where conditions and not joins ), the time taken to execute the query will always be constant for a given table, in this case, 34 sec, without the indexes, or are there other parameters which can make the execution time to vary with significant differences, when queried different columns.
The query execution times depends on a lot of other factors but we can certainly say that the pointed queries will require the same number of Disk IOs.
The query execution time will depend on the number of rows being fetched, current load on the DB, IO tuning of the DB, Cache settings, etc.
One thing that would impact the lookup time the most is caching policy and buffer size which would mean a large part of index can be kept in memory leading to quicker execution.
hey, i have a question let, suppose 1 row have 700 bytes of data, and cell block in disk space is of size 600 bytes, then how this row data is going to store?
That's a great question; glad you were thinking of edge cases. Read about TOAST in PostgreSQL.
one of the best videos i have seen till date.. u r a gem of a person...
But,. one doubt, here in RDBMS we were able to know the block from the id very easily because we knew that every block has a fixed and SAME number of rows stored in it...
but, how will the indexing explained in this video work for NoSQL DB?.. as the amount of data / Number of rows stored PER BLOCK is Not constant .. thus ,after looking into the indexed table , we dont know , the given id is to be found in which block????
@DurgaShiva perhaps the index table in such a case must also be storing the length of record (in bytes) to help the DB fetch record for exact size. But am not sure, plz confirm how this is handled, @ AsliEngineering...
I don't know why channels uploading 100 videos on z-index/ basic js are more popular than this goldmine. As always great content sir
Thank you for resonating. As you found the stuff I put out helpful, it would be great if you could spread a word across socials. It would help people become more curious and overall better engineers.
Thanks again!
Hi Arpit. When we used the age index table, we got row ids = {1,4}. Why did we only require 2 blocks search to find records with ids = 2 and 4? How did it know only those 2 blocks will contain rows with id 2 and 4, shouldn't all blocks be searched for this?
Using the index we narrowed down the row ids we are interested in. When we go through the table to look for the rowwith those IDs we can leverage the storage structure used to store the table. This is where the magic of B+ trees come in for the relational databases.
By default all the tables/databases are structured to make the lookup by primary key very efficient and this is something that powered by the core storage structure (B+ trees for relational databases). So when we are looking for the relevant rows with particular IDs the database engine would know which all block to reads and how to read them [typically done by managing and maintaining the disk offsets].
This makes are entire process super-efficient and not needing us to read entire table to find rows with specific IDs.
Hope this helps.
@@AsliEngineering Thanks for the reply. What you said makes absolute sense but I had another doubt after reading this. What if a table doesn't have a primary key, can indexing still work in this case? If yes, what will the index table point towards now as there is no primary key to point towards?
Thanks for the explanation bro
Thanks for asking this, I had the same doubt.
for age = 23 we got record ids = [1,4]
so we read 2 blocks which were adjacent. But lets if my record ids are [1,4,99] for age = 23
then we need to check all 34 blocks right since 99 record id will be present in 34th block?
If id corresponding to age==23 were present in all the disk blocks,34 blocks then read query will become slow in this case. It would have taken 36 seconds. How to optimize that?
Excellent question.
A database engine can optimize this by not iterating over index when it finds the cardinality of resultset is almost equal to the number of table rows. This is why every database has the query optimization phase.
@@AsliEngineering will spend some time reading about this query optimization phase
@@AsliEngineering but even to find cardinality of result set on index search, it would still can process all blocks, right? So anyhow time is wasted
@@prachiagrawalcipher But what about time consumed in maintaining index in ordered form
What if for age==23, we end up with two ID's from the index table: id 1 & 9999. To fetch the records from main table with these ID's, we have id 1 in the first block [ 1 block is read ] and to reach the block in which id 9999 exists, should DB go through all the blocks ? Hypothetically let's assume, id 9999 exists in the last block : then isn't the time taken for getting these records will be 34 blocks + 2 blocks ?
@AsliEngineering I have couple of questions here: 1. You mentioned that age index will be sorted in some order. Does that mean during insertion it'll try to move records to identify the correct place for the inserted record to maintain the sorting order. Will it have negative impact on performance. 2. In your example, ids with age 23 was exhausted by block 2 but what if there was one more record which is part of last block. In that case the response time will go much higher. Please help me with the answers in order to clarify all these doubts.
that's why you have B+ trees. I have a video about it on my channel
Can you tell how you choose indexes optimally?
If i have 3 columns
Id, fistname, lastname and i want to query by firstname , bylastname,byfirstand lastname how many indexes and what index should i make?
Index on firstname:
If you frequently query by firstname, having an index on this column can significantly speed up those queries. This index will help the database quickly locate rows based on the firstname.
Index on lastname:
Similarly, if you frequently query by lastname, having an index on this column can improve the performance of such queries.
Index on both firstname and lastname (composite index):
If you often query by both firstname and lastname together, a composite index on these two columns can be beneficial. This index can speed up queries that filter based on both the firstname and lastname simultaneously.
The number of indexes and which indexes to create depend on the query patterns of your application. Here's a summary:
If you frequently query by firstname, lastname, and both firstname and lastname together, you might create three separate indexes: one on firstname, one on lastname, and one composite index on (firstname, lastname).
If you only query by firstname and lastname individually (not together), you might create two separate indexes: one on firstname and one on lastname.
If you rarely query by both firstname and lastname together, you might prioritize single-column indexes on firstname and lastname separately and skip the composite index.
Remember, each index adds overhead during data modifications (inserts, updates, deletes), so you should only create indexes that are necessary for improving the performance of your queries.
one thing that is clear from this is indexing comes with the cost of making writes slower. But Can it make read slower also? Like In cases where we have to return almost entire table?
In case where we have to return almost entire table, query optimizer may choose not to use indexes
I have a question, How do I know in reality size how a block is?
Also the example in the video in the case of 1 record with age = 23 is in the last block. then the number of block reads is
2 (index block) + 34 (record block) = 36 is even more time consuming without indexing.
Does the database have to read the blocks in turn to find the block containing the matching id
The size of the disk block is configured by OS typically 4KB.
The DB does not have to read all blocks to find the block containing row with a certain ID. this is where B+ trees come in. It is O(log n) lookup.
Lets say you got the ids from index - [1, 4]. You still need to iterate through all the blocks to check whether 1 or 4 is present in that row or not. Explanation seems incomplete to me. How do we get block from ids?
B Trees
@@AsliEngineering thanks
Hi Arpit, Great Content Thanks, I Have This Doubt What If Each Block Has A Entry Where Age==23, So Our result buffer will hold all the IDs and each id will be stored in a different block, so in that case, our total will be 34 sec for reading all blocks and 2 sec for index scan so total time is 36 sec but in previous approach without an index it was 34 sec, so how to deal with such situations.
During query evaluation, database runs an optimization and checks the best approach. It does this by maintaining the cardinality of each indexed attribute.
Here as it would see a skew, it would not use index for evaluation.
@@AsliEngineering
Got it Arpit Thank You 😊
Hi Arpit as our index table is sorted we can use binary search to find the age =23
The tree structure above the leaf node in B-Tree is actually doing an n-ary search.
Hey Arpit, thank you for the great explanation!
Have one doubt, how does the database know that from [1,4] 1 exists in block 1 and 4 exists in block 2?
Is there another data structures which stores this ?
+1. Same question
I guess id's are the address to the blocks, so that we can directly jump to that address and fetch the data.
B+ trees.
Hi Arpit, I got little confused when you said index is on id column instead of age column at time 13:26. Later it got clarified that it's age column.
My bad. Flow flow me ho gaya. Will be extra careful going forward.
I don't know why no one pointed out but the time to compare is 34 seconds and 4 seconds not 32
5:07 why it so? why full block size is read instead of the one which we are interested in?
Because that is how disk IO works. When you read anything from the disk, your file system reads the entire block (that contains the intended region).
Hey 👋 Great content brother.
Which software do you use for the notes? And do you use ipad pen ?
Thanks
Thanks. I do use iPad with Apple Pencil.
@@AsliEngineering BTW, Which app is this
One very basic doubt.... index is returning the ids of the rows..and NOT the pointers to the block(which i am not sure can even be stored and returned)...these ids may be present at the very LAST block of the storage, due to which we will need to traverse the WHOLE blocks.. which finally defeats the concept of indexing, and this video seems to be irrelevant..
Please guide me regarding my question
Maybe I missed that but I didn't get how system is deciding that ids (1,4) are available in block 1 and block 2? Are we checking 1 by 1 in a linear-search fashion?
I have also this same question, how the processor will decide which block it needs to read to get the data it founds from indexes. @Asli Engineering by Arpit Bhayani.
If you look at B+ Trees you will get the idea. The B+Tree stores the location of the disk block(shown here as the id for easy illustration). So instead of 1 and 4 the address/offset to the disk is stored and then those blocks are read by the engine.
@@kps4881 thank you for reply. But can you please explain a bit more in terms of address/offset and block 1 / block 2?
@@gauravraj2604 The leaf node of the B-Tree or B+Tree is a pointer to the offset of the disk block which contains that actual data. So once you traverse the tree and reach the leaf, you get the pointer to the disk block that is used to read the data from the disk directly.
What software is used in this video to write notes, feels good to read from the notes.
Description has the information 🙌
❤️🔥🔥
what device or software do u use for writing content while u teach?
GoodNotes on iPad
✅
how will the index be stored if there is no primary id in the table ?
Order of insertion.
I discovered your channel today while going through your blog on replication. I like the explanation but I think video title should say how indices make database reads faster. Write performance decreases because of additional indices.
Excellent suggestion. Altered the title. Cannot edit the video now, but I get the point. Thanks a ton for the input.
I think this is not always the case if index update is async.
isn't index stored as B Tree?
Yes. The Index is stored as Btree. The other popular option is Hash data structure.
is it intentional to blur the video?
uska tab ka resolution kam hoga