How do indexes make databases read faster?

[@aayankhan5198]

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.

[@AsliEngineering]

🙌🙌 areeee thanks 🤘

[@pankajgaur3360]

indeed

[@harshitanand7349]

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.

[@SR-we1vl]

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.

[@nayabrasulshaik8765]

To the point 😁

[@nytlyf2085]

21:49 perfect example of a range query optimization.

[@mridulmaurya8383]

seriously blown out by how you explained such a complex thing in a simple manner. Thanks man!

[@sarangbondre]

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?

[@dhineshrathinam8756]

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

[@sheersendughosh]

Every college should mandate your videos as part of their curriculum, your content is just knowledge bomb! Wish had known this in college days. You have sparked my curiousness thanks a lot!

[@singh.aadarsh]

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. 👍👍👍

[@jspnser]

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.

[@ankitverma1790]

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

[@agrittiwari5485]

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.

[@vasiovasio]

Great video. I just want to tell you that you have a typo on your thumbnail image - "indices" instead of indexes.

[@jaskiratwalia]

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!

[@kalpeshmali1476]

Wow aaj pata chala 😂 literally Gold 🔥🔥🔥🔥 keep it up sir

[@santosh_bhat]

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 ?

[@venkateshnaga4550]

can u pls help here @AsliEngineering

[@victorsolomonmachinelearning]

Exactly what I said to myself. Hahaha. By the way he explained it, the aim of indexing is defeated in this case

[@Mr.Mishr4]

Great Video ! But I just want to add one thing: when you mentioned adding age as an index and that it's sorted, this implies we can use binary search operations to find the required age's start and last values. This improves the time complexity from O(n) to O(log(n))for searching.

[@ahirjoy]

Waiting for your book on System Design one day. There is real need for such book in the market. Keep inspiring.

[@codingwithkhurram]

You did an excellent job with the explanation, and I really appreciate the clarity and detail you provided! Your effort in making the concepts clear and understandable is commendable.

[@kashyapsharma8721]

Indices explained in the most simplest of terms. Excellent video , thank you Arpit.

[@saurabhsuman4960]

Thanks Arpit. These explanantions makes learning fun.

[@timmytesla9655]

Amazing breakdown of how index works.

[@israaezzat2353]

you nailed it !! seriously its the best explanation I have ever seen for Index thank you 🙏

[@chandruts.2579]

Great video! The explanations were crystal clear and easy to follow. Thankyou Asprit Ji

[@meeta890]

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.

[@chandrachurmukherjeejucse5816]

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

[@AsliEngineering]

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!

[@SurajSingh-tz1wr]

A complex topic explained in such a simple words. Nice!

[@vamsireddy5051]

Really superb explanation, you not nailed normally but nailed it deeply 🙌

[@aruprakshit7218]

Why don't you have DSA course? Your teaching is top-notch.

[@shabnamhaque2003]

how wonderfully explained. sir you have no idea how helpful this video is.

[@myironlung9651]

Thanks! You're a nice teacher!

[@kanikabhatia4171]

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?

[@pratibhasharma4006]

Inspiring content. Thanks a lot sir

[@RTXXONn]

wowww so simple yet so elegent.

[@adamyatripathi2743]

Maza aa gaya! Behtareen! 🔥

[@DemystifyFrontend]

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 🙏🙏🙏

[@udayakumarsakthivel6285]

You made index content as so simple 🤪. Great explanation 🎉

[@soodankit1993]

@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.

[@AsliEngineering]

that's why you have B+ trees. I have a video about it on my channel

[@muskan_bagrecha]

This just piqued my interest. Guess I am going to dive further into these topics. Thanks Arpit.

[@raj_kundalia]

Thank you, Arpit!

[@PrdpPtl-j4b]

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.

[@LeoLeo-nx5gi]

Arpit bhaiya trust me this was really awesome (though I knew about indexes but still learnt many new things), Thanx ^_^

[@biswaMastAadmi]

Beautiful explanation brother!

[@cur92lyone]

Arpit - you're truly talented, with such in-depth knowledge. No wonder, your career trajectory reflects that :) Keep rocking - onwards and upwards. ALso, Pleeeeease NEVER STOP MAKING SYSTEM DESIGNING VIDEOS! EXCELLENT! 😊

[@gulabsinghsikarwar7447]

Great in depth Explanation ! .

[@97vaqasazeem]

Thanks alot i learn alot from your content it is clear and to the point !

[@varunkoranne6872]

The content and explanation is just too awesome

[@Shivam-sl4sp]

This is just too good! Thanks man.

[@yusufmirkar6508]

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

[@Sanjay-pu4sp]

Fantastic! You have a real flair for teaching mate!

[@bheemireddyvamsi7042]

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.

[@abde2849]

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...

[@parambharti7095]

Very informative video. Thanks @Arpit Sir.

[@nimitkanani1691]

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.

[@deepakkothari2850]

This was wonderfully explained 🙏

[@JardaniJovonovich192]

Great Video, Arpit !! It'd be interesting if you could make a video on BTree Indexes and clustered BTree Indexes.

[@AsliEngineering]

Soon :)

[@kps4881]

Till Arpit makes one you can check out this video. kzbin.info/www/bejne/l4vNiqVubNdkmJo

[@rahulkumarmishra1638]

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.

[@AsliEngineering]

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.

[@rahulkumarmishra1638]

@@AsliEngineering Got it Arpit Thank You 😊

[@theoptimaldeveloper]

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?

[@Avinashkk360]

In case where we have to return almost entire table, query optimizer may choose not to use indexes

[@prashantgupta387]

12:51 great content 😁

[@RutwijGhadge]

Nice and clear explanation 👍

[@adwaithssundar1620]

Superb explanation!!

[@abhishek3835]

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?

[@AsliEngineering]

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.

[@abhishek3835]

@@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?

[@suraj-upadhyay]

Thanks for the explanation bro

[@manchukondamanoj]

Thanks for asking this, I had the same doubt.

[@shreyanshnanavati]

Brilliant Video Arpit :) , Thank you so much, clears alot of concepts around Indexes :)

[@AsliEngineering]

Thanks man!

[@drunkcse7476]

Please make a video on types of index (sparse and dense) and real life use case

[@aditigupta6870]

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

[@ayushjindal4981]

Very nice explanation !!

[@roshnigupta9296]

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.

[@AsliEngineering]

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.

[@HimanshuKumar-xz5tk]

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?

[@AsliEngineering]

B Trees

[@HimanshuKumar-xz5tk]

@@AsliEngineering thanks

[@abhijitmitra4665]

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??

[@jpnr8]

Thank you for lesson.. its awesome..

[@gauravraj2604]

Hi Arpit, Amazing explanation. Thanks. I wa wondering how this block size (600B in your case) is decided?

[@AsliEngineering]

Typical size if 4kb. I took 600 as an example. Not too small not too large is the only criteria

[@abhishekvishwakarma9045]

Really liked how you explain things so easily with that much detail, totally awesome arpit sir 😁

[@harshildoshi3299]

Loved the way you simplified the concept. Would you recommend any book(s) for the concepts includes Indexing, Cursor, Query Optimization etc?

[@mahimanbissa8308]

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?

[@AsliEngineering]

Read about B+ trees and how they work. That will help you understand how rows are fetched.

[@420lomo]

Recently discovered your channel, very engaging content! Thanks

[@SabyasachiMohanty-x3q]

Thanks bro!! Loved the content... great one!!

[@KK-kl7se]

Good explaination , btw what tool are you using in your explanation @Arpit

[@HowTo-bk2jn]

Great explanation!

[@karanbangia14]

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?

[@navinmittal4809]

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.

[@AsliEngineering]

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.

[@santoshbhatnagar2155]

Can you share an example for the question being asked please.

[@ShubhamGupta3110]

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?

[@its__aakashg_]

Thankyou .. it was really informative

[@jayeshlokhande6367]

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 ?

[@SumitSharma-bb5ik]

+1. Same question

[@SumitSharma-bb5ik]

I guess id's are the address to the blocks, so that we can directly jump to that address and fetch the data.

[@AsliEngineering]

B+ trees.

[@DurgaShiva7574]

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

[@shrutimath3330]

Amazing content 🙌

[@angnguyen-vn2on]

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

[@AsliEngineering]

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.

[@abhishekpathania7093]

1. Are indexes sorting again & again on inserting new data. 2. then does data also move from 1 block to other block after index resorting.

[@AsliEngineering]

1. They use data structures that keep data ordered. No need to sort again and again. Check b plus trees 2. Yes. And that's rebalancing phase of b plus trees

[@harpalsinhjadeja5571]

I don't know why no one pointed out but the time to compare is 34 seconds and 4 seconds not 32

[@gauravraj2604]

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?

[@gauravgupta5530]

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.

[@kps4881]

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.

[@gauravraj2604]

@@kps4881 thank you for reply. But can you please explain a bit more in terms of address/offset and block 1 / block 2?

[@kps4881]

@@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.

[@navinmittal4809]

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.

[@AsliEngineering]

My bad. Flow flow me ho gaya. Will be extra careful going forward.

[@nytlyf2085]

This guy is good!

[@ramprasadthakur1682]

Hi Arpit as our index table is sorted we can use binary search to find the age =23

[@AsliEngineering]

The tree structure above the leaf node in B-Tree is actually doing an n-ary search.

[@sunilbabu588]

Thank you man.

[@prachiagrawalcipher]

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?

[@AsliEngineering]

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.

[@prachiagrawalcipher]

@@AsliEngineering will spend some time reading about this query optimization phase

[@sahil0094]

@@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

[@rohansharma8618]

@@prachiagrawalcipher But what about time consumed in maintaining index in ordered form

[@vengateshgv8824]

Hi bro. Can you please tell me. Is index take more ram when compared without index?

[@Roger-kv6jw]

well explained !

[@godbhaigod]

If Index is stored in separate block, then in MS SQL serve, Why Rows are sorted inside a table when we define clustered index and Rows remain unsorted when we define Nonclustered index?

[@kirankumargunturu8517]

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

[@Avinashkk360]

I think the assumption is table stored in B+ tree structure.

[@niteshrawat576]

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?

[@niteshrawat576]

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.

[@akashagarwal6390]

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?

[@AsliEngineering]

have a members-only video on that already.