‫One of the most important fundamentals to understand and databases are the back end of tables and indexes,
‫and how are they stored on disk and you going to see me mention these fundamental, you know, concepts
‫and pieces?
‫And I want you to understand them before jumping into deep into the course.
‫So this lecture will discuss these different concepts, how tables are and indexes are stored in disk
‫and how they are queried.
‫And what is the cost that is associated with these knowing these concepts?
‫Let's jump into it.
‫So here's all of the storage concepts and not really just storage is just the operations that are performed
‫on the storage itself.
‫So we're going to assess what is a table from a logical point of view.
‫We're going to discuss the role I'd consider the unique identifier of the role we'll get to discuss
‫what is a page.
‫We're going to discuss what's in IEO, a heap index, data structure, Beatriz.
‫And if I know going to give you an example of how a query performs on the heap versus an index, let's
‫jump into it.
‫So we have here a beautiful table with a bunch of columns, right?
‫And so these are the actual field, the columns, and this is a row.
‫Obviously, you might say that I work with databases that don't have rows.
‫They have documented the same Briody same concept.
‫Once you take that idea off row, you can convert to back into.
‫At the end of the day, it it's all bits and bytes and and the storage model just understands that.
‫And that's where I want you to understand this.
‫This rule, this is a call.
‫So what is the concept of photo ID here?
‫Usually databases.
‫Don't work with the fields that you provide them, some do right, but most databases create their own
‫system maintained row.
‫Right.
‫And this is the real idea effectively, and this is a position in the role itself to a uniquely identified
‫this particular role ideal right in Postgres.
‫This is also called tuple I.D. effectively.
‫Right?
‫There's another important concept to understand, right?
‫Nothing.
‫Nothing so special.
‫In my score, for example, the primary key becomes that pseudo rule IDF actively.
‫Right.
‫But in Postgres and some other databases as well and you roll ideas created on your column.
‫And that is how it is referenced effectively.
‫So what is a page, really?
‫So if we really thought about this stable right as we're looking at this logical table, a bunch of
‫columns and rows, what depends really on the storage model, whether it's a role store and a columnist
‫that I really want you to watch that other lecture where I talked about role versus columnist or how
‫are they physically storing it does really matter.
‫Roles are stored on these logical pages and pages are really nothing but a fixed size memory location,
‫which translates to desk location as well of of a of a bunch of bytes.
‫That's it.
‫It's a fixed size.
‫Usually it's fixed size.
‫Right?
‫And then you can put the row in the page.
‫So technically, a page can fit many rows.
‫Now it depends how many rows.
‫It all depends on the size of the row, right?
‫And the size of the columns and the size of the data types of these columns.
‫So the database really doesn't really read just a single row say, Oh, go, really read me.
‫Wrote them 4000 now.
‫It's not like a ram.
‫RAM is byte address where you say, Oh God, give me that particular byte location and just go read
‫it.
‫That's a random access memory, right?
‫RAM.
‫No disk, on the other hand, actually just reads a page, right?
‫And you tell me, Oh, go, go make an Io and fetch me this much data, right?
‫And when you do an issue, this input output, you get a page or more than one page.
‫It really depends on that.
‫The disk partition, how did you partition your, your format, your formats, your your hard drive
‫or SSD?
‫And it depends on so many other factors like that that the operating system as well.
‫But when you actually read, you get so much stuff, you get one page or more.
‫It really depends.
‫But the beauty of this is one page can have many, many roads and write.
‫Each piece has a fixed size like guess the default size is eighth-grader by.
‫It might be quite, I believe, a 16 year old, and you can configure those.
‫So if I, for example, say each page holds three rows pride in this particular example, that means
‫for one thousand one rows, you divide it by three.
‫You get around 333 pages, right?
‫And these pages are stored on disk, right?
‫And when you look at them in the disk, it's just a bunch of little ones and zeros, right?
‫But they physically have a start and an end, which you define as a database.
‫So this is how you look, and this is very critical to understand it is not just theoretical stuff.
‫This is what makes some breaks a database.
‫This is what makes a query slow or fast.
‫Understanding how many pages are you pulling?
‫How many ideas are you making?
‫Because that's what you what it would actually have pages.
‫What does it tell you?
‫And I was an operation that reads request to disk.
‫We try to minimize this as much as possible.
‫This is the currency of a database.
‫The list i o you make the faster you records.
‫That's what we need to make.
‫So what does that mean?
‫And i o can fetch one page or more, depending on the disk partitions.
‫I don't know about that.
‫And I cannot read a single row.
‫It's just a page with many laws in them.
‫When and when you do that, you get many rows for free.
‫You don't get to say, Oh, I want this page, but I don't want this stuff.
‫Sorry, you don't get to do that.
‫Oh, I want this page, but I don't want the date of birth.
‫I want this page.
‫But I don't want the names.
‫No, you don't get to do that.
‫That's why select Start is very expensive.
‫That's why I select a name is very expensive as well.
‫Right.
‫Because if you do select name from table, because what you're already going to the table, you're doing
‫the page.
‫If it's a roll store, you're getting everything right.
‫We're going to talk more about that in the the and the course.
‫In the database has to filter out what you don't want and throw it, um, throw it away.
‫The cost of this realizing the bites back to the memory in memory structure for the database to process
‫is expensive, right?
‫So you want to minimize these ills about expensive same ideas.
‫An operating system Some eosin operating system goes to the operating system cache, and this is specifically
‫true for in case of Postgres, post-Christian rely heavily on the operating system cache, so an i o
‫doesn't really mean going to disk so it could go to a cache that the operating system defines.
‫So you're going to hear me as well.
‫Talk about this a lot in the course heap.
‫What is a heap?
‫A heap is exactly what we talked about here.
‫A heap is a collection of pages that represent points to your data table.
‫It has everything above the table itself, so everything in the table is in the heap.
‫We call it the here because it's a special data structure that has pretty much all the data, everything
‫right?
‫And that that makes it expensive to query because it has a lot of data, right?
‫So this is where the actual data is stored and everything.
‫Traversing the heap is expensive, as we need to read so many data to find what exactly we want, right?
‫Because usually when you look, when you read stuff from the heap, when you try to find something you
‫find, you're trying to be looking for few things.
‫But the heap gives you everything.
‫And that's costly, right?
‫This is why we need indexes that help that help tell you.
‫Tell us exactly what part of the heap we need to read.
‫We don't need to read every single page in the heap.
‫I want to know what page exactly to jump to, to read just that page.
‫You can do that.
‫And the desk is a go read me page three, three, three, three, three and above.
‫You can do that, but you can't say, Oh, go read me raw seven row if if you say, go read me Ross
‫Avenue, get a good page two and maybe Page three and anything that's next to it effectively.
‫Let's talk about the indexes and index is nothing but another data structure.
‫No, magic is just a bunch of other data structure that helps you pinpoint exactly where to go into
‫the heap.
‫So you can fetch that information in an efficient manner.
‫So an index is another data structure separate from the heap and has pointers to the heap.
‫And these pointers is just literally numbers that point to the row ID that we talked about, and that
‫already has more metadata about the page in the heap that we need to pull it.
‫It has part of the data and used to quickly search for something.
‫You can index one or more column, uh, in the index effectively to create this data structure.
‫And this data structure uses something called bigotries, which I have an entire section talking about
‫effectively.
‫So, yeah, because you cannot index everything you index exactly with the things you need to search
‫for.
‫Once you find a value of the in the index, you go to the heap to fetch more information where everything
‫is there, right?
‫That's that's the point of the heap.
‫Index tells you exactly which base to fetch in the heap.
‫And instead of taking the head to scan every page in the heap, the index is also stored as pages and
‫cost i o to pull the entries of the index.
‫Because guess what, when you when you think about the index, it's not something magic, right?
‫It's a bunch of guess what a bunch of another data structure usually be tree and that be tree.
‫You need to read it in order to understand to pass this content, right?
‫And this leaves on desk because when you spin up the database, you need to read the index from desk
‫and pull it in memory.
‫Some indexes fit in memory, others don't.
‫If you have an index that is so large, it doesn't have to fit in memory that makes in searching the
‫index to know what to pull right from the heap can be expensive, and this is what I want you to kind
‫of understand and pinpoint here.
‫More and as the more can fit in the memory, popular data structures for indexes as Trig can be listed
‫at a structure.
‫Brennan indexes, you know, many other type of indexes.
‫Learn more on the B3 section.
‫All right, so this is how it looks like on index on disk.
‫This is a very simplified if it was guys, so take it with a grain of salt.
‫This is not exactly how it looks like, but it helps.
‫Interesting.
‫So this is the heap.
‫So we have a page.
‫We have a row ID one.
‫This is the price and probably their employee ID, the name, the date of birth, the salary and then
‫immediately the next employer or stocks, right?
‫It's in the same page.
‫Roll it to twenty nine and then Ali five two.
‫And then this ends page.
‫Image one.
‫I simplified it.
‫It's exactly identical to this, but I just said roll five, four or five six because of three rows
‫in a page.
‫Remember that that that was our condition here in this particular example.
‫Seven, eight nine based two.
‫So 10, 11, 12 and Page three ended it.
‫It added it.
‫A Page 33 will have will have three rows the thousand nine, nine, nine and 998.
‫Well, this is the heap, right?
‫But in the index, if you think about in the index, it like, let's say, I indexed on employee I.D.,
‫which is this 10, right?
‫So you you're going to see only the employee ID here.
‫So 10, 20, 30, 40, 50, 60, 70, 80, 90, right?
‫And then did it add it up until 10000, which is the last employee employee 10000.
‫OK, I have all the employees here, but that's just their ideas.
‫And look at what do we have here?
‫This is the point we talked about.
‫Is this OK?
‫Employee I.D. 10 lives in row ID one has our I.D. one and lives in Page Zero, right?
‫Employee ID 20 lives on Page Zero.
‫Android Auto Employee number one one zero.
‫It lives on Page three and he has a.
‫ID 11 and so on.
‫Right this way, if you search the index and searching the index is just another Io, as we talked about
‫it now, it's not sequential.
‫As I am showing it here, it's more a little bit complicated than that.
‫It's a B3 structure.
‫So it's that actual three where you go to the left, if it's less and go to the right of it's more are
‫going to talk about that in details.
‫But take this with a grain of salt as an example.
‫So let's say I want to search for employee, I don't know, 40, right?
‫So 40, I build this page.
‫So I did.
‫Didn't I own the index?
‫Oh, I found four employee 40.
‫But hey, wait a second.
‫I don't want employee 40.
‫I want their name, for example, or their salary.
‫Or you need to go to the heap.
‫What do you do?
‫How?
‫Well, how do I know which page to go to the hip?
‫Well, employee, 40, have his a raw 84 and it's page one.
‫So immediately you do and another I own the heap says, Oh, give me page for page one and give me employee
‫a story.
‫Raw ID four.
‫So you go to the whole idea for you.
‫Discard five of the six because guess what you did and I know you got five and six.
‫You cannot.
‫You cannot escape that.
‫With that, I'll give you all the stuff right?
‫And you gave you five and six and and their birthday, you got the salary of six.
‫You get you get the d'urbervilles there.
‫You get it their name of six, you get all this stuff, but you only take exactly what you want from
‫for effectively.
‫The database does all this magic behind this.
‫So think about it just that.
‫So this is much more efficient, right?
‫If this query is fast and if this square is fast furious, asking for more is going to do more jumps
‫here, right?
‫Let's take an example.
‫So let's say I don't have an index.
‫I only have a heap and I want to do select star from employee table, where employee ID equals 10000.
‫Well, in this case, guess what?
‫Employee doesn't have an index, right?
‫So what do I do?
‫Well, I don't have a choice.
‫I have to go query Page Zero, as is.
‫How many rolls do we have?
‫We have Raw ID one, which is 10, 20 and 30 employed, 10 employee I.D. 20 and 30.
‫Oh, none.
‫None, none.
‫Discard the page.
‫Go to the next page.
‫Page one four five six seven eight nine.
‫Nope.
‫Up until doing fitting all these pages, this is so expensive.
‫Some, some databases does a parallel threading multiprocessing to kind of walk this structure from
‫by using multiple threads from down and bottom, from down to top.
‫And in parallel, to scan.
‫But in general, it is expensive because the last page happened to be the one that have employed ten
‫thousand.
‫So we did a lot of ways to fix that.
‫So that's that's what our index lets doing with that index.
‫So now the query with the index, in this case, we're going to query Employee ID ten thousand.
‫And here's with the B3 query actually takes place and it goes through a three until we find exactly
‫the page that we need to look at and one the moment we find a page in the index o is page and we go
‫to the page and then we find that exactly employee ten thousand.
‫Right.
‫And this is ORide Thousand and its page 333.
‫So once I got that tuple that information, now I go to the heap and they say, OK, go page three,
‫three three, and Paul wrote 10000 and returned to the user so immediately we know where to which page
‫to pull and immediately we get all the information.
‫And then finally, I have some notes here that I just added so we can discuss and end this lecture.
‫Sometimes the heap table can be organized around this single index, right?
‫So we did show that index is a separate data structure from the heap.
‫But sometimes the heap, as you can, as you saw in this lecture, is not really organized.
‫It's not ordered right.
‫But the heap can be ordered around the index.
‫And in that case, it's called the cluster index.
‫And I talk about it in this lecture as what in this course?
‫Sorry.
‫And it's called also called the oracle terminologies called iottie or sorry.
‫It's called index organized table iottie, right?
‫So I just fixed it.
‫So, yeah, so this is called an iottie write and index organized table where you have the table organized
‫around a single index of activity.
‫And this is called a cluster index and has a pros and cons.
‫Cango can.
‫I can't go into this in this lecture, but I'm going to talk about it in other lectures as well.
‫Primary key is usually what is called primary as a cluster index, unless otherwise specified and whenever
‫you hear the term primary key there.
‫Means it's a cluster, and next, usually unless his boss, Chris Paul, post-GST primary keys, is
‫just the secondary key, right?
‫So my school a.B always have a primary key.
‫It's always have a clustered index.
‫So if you define a primary key, the table will be organized around that index.
‫So be very careful about what data type you pick.
‫I talked about this a lot.
‫The idea of having a, for example, a new idea which is truly random in a cluster index just kills
‫the performance when it comes to writing.
‫Because now if you insert a new idea, random thing.
‫Now the heap have to be organized around the index, which is your idea, which is random.
‫So you're going to be he be hitting multiple pages because every new idea is random, so it will and
‫will live in another completely random page.
‫And this scattershot is very, very expensive.
‫And I talk about it and many other ask questions, guys.
‫If you want me to explore more of these products have only secondary indexes, and all indexes point
‫directly to the Real ID, which lives in the heap.
‫So this is different than the primary key, right?
‫So in the case of if you have a primary key where you have that kind of clustered index, the primary
‫key itself is a kind of almost like a user defined field, right?
‫But the lack of any other index will point to that primary key here.
‫But in Postgres, everything is a secondary index.
‫We have this role idea, which is a system maintained field that every index point to the Real ID,
‫which means if you edit anything in focus, all the indexes get updated.
‫That's a cost that you have to be in to understand, right?
‫It's just all makes sense when you understand these low level things.
‫That's why I wanted to make this lecture and find an to make.
‫I mean, we talked about what a table is talked about there wide, which is really it's a system maintained
‫field that some databases at, some don't.
‫Some rely on an existing primary key that the user defined lookup a page a page has.
‫It's just a fixed size, right?
‫Some pages are dynamic, but let's talk about fixed size just easier to deal with fixed size pages,
‫8K and Postgres 16K and equal.
‫And you can put arrows in them.
‫You can put columns on them.
‫I can organize the page around columns, which is something I'm going to talk about.
‫And it looks like you're right.
‫I o gives you one or more pages.
‫You don't you don't get a roll or a byte in an IO.
‫You get a lot of stuff.
‫So the key here is if you do it and you get everything you want in a single i o, that's the beauty.
‫That's the efficient dial.
‫You want your audio to be efficient, heap data structures, right?
‫We talked about that index did as Dr B threes, and we gave you some examples.
‫All right, guys, I'm going to see you in the next month.
‫Thank you so much.