‫What's going on, guys?
‫My name is Hussein, and I want to take a few minutes to explain the difference between sequential table
‫scan and an index scan.
‫And a bitmap index scan, which is something specific to Posterous, but regardless, it's very, very
‫clever.
‫And I want to take a few minutes to explain the difference between three.
‫You might have a more familiar with the sequence of sequential sequential tables scan as full table
‫scan, but that's just about terminology.
‫How about we jump into it and play with this little bit?
‫So I have a table here called grades and it has an ID, which is a primary key and it's a LTA increments
‫serial have a primary key, which is an index.
‫I have an index on the ID field is just a one, two or three incremental value of a name which not index
‫or anything like that.
‫I have a grade field G which indicate this is thinks of all this like a grade of students and G is a
‫value between zero and one hundred.
‫And there is an index on that grade field that includes as a Nunk key value.
‫Also the ID feel, which is pretty, something we talked about in many videos.
‫So now what I want to do here explain many aspects of how can I query this table to retrieve certain
‫data and pay attention to this.
‫I'm going to explain, do and explain, because I don't really interested in the results.
‫I want I just want to know what postcrisis is about to do when I want to ask you this.
‫So I'm going to select name the name of this student from the grades where ID is equal a thousand.
‫Right.
‫Whether there is a specific ID.
‫And the moment you do that, you can see that that postcrisis is going to use an index scan using the
‫grades primary key, which is the ID, and then provide the values using the index condition on the
‫index.
‫That's the ID equal thousand and is going to pull.
‫We know that is going to build one value.
‫Right.
‫And that explains a lot why we have one goal once we pull that row.
‫Now the index is responsible to go back to the table to bring the name field.
‫Why?
‫Because the name is part of the heap.
‫It's part of the table, which is part of the hip, which is another data structure, the index is a
‫different data structure.
‫Now, if I if I if I do this, for example, I like less than that's a hundred.
‫So I'm bringing around ninety nine value.
‫So Polska still decided to do an index scan.
‫So what, what, what happened here.
‫Let's go through exactly what happened.
‫So we brought ninety eight rows in this case.
‫What Postgres did, it says OK you want anything.
‫Any student that has an idea.
‫Less than one hundred, which is kind of a silly query if you think about I don't what database, what
‫the database decides says OK, I'm going to use the index to do an index scan on the on the ID on that
‫index and then go scan one by one and find find anything that has less than one hundred.
‫And that's very quick to do in a B three, especially that we kind of have a clue of how many rows is
‫going to get back.
‫So it's OK, I want anything that's hundred, anything that is greater than one hundred, just toss
‫it away and so it knows that is going to get values ninety nine or less because maybe something was
‫deleted and as a result it used an index.
‫And for each value that it finds, it finds the page where that rule exists and goes back to the heap
‫to pull that page which kind of have one or more rows and then pulls that value.
‫And this is called random access.
‫So four ninety nine, it went to the page of the heap that it did that four ninety eight for all the
‫rows.
‫So this is called random access.
‫So you can see that this can get slow if you have a lot of rows.
‫So let's go do something ridiculous.
‫By the way, I have around fifty million rows in this table, so I'm going to do it greater than one
‫hundred.
‫Polska is actually smart enough to know, OK, I expect at this table this query is going to be insane.
‫So look what that database did here says, OK, it is better than hundred.
‫I have what is the maximum?
‫It it has them statistics.
‫Right.
‫And I Kalka this a statistic by doing analyses grades and when you do analyze grades it will calculate
‫some statistics on the table, says, OK, this table has 50 million and this guy wants anything that's
‫greater than hundred that's going to bring 50 million rows back.
‫Is that 50 million to five million?
‫Right.
‫I forgot how many rows I have in this table.
‫So five million.
‫So bring all of those properties back.
‫Well, wait a second.
‫Scanning the index.
‫And every time I find a ruined the index, they're satisfied 100, which, guess what, almost all the
‫rules will satisfy that except the hundred that is listed in the hundred.
‫Right.
‫I'm going to go and jump.
‫That is extremely expensive to jump back and do a random exit.
‫So both of us decided to do a sequential scan.
‫What was that sequential scan and says you don't want.
‫Let me just let me just jump to the table and do a sequential scan on the table.
‫It's way cheaper to do a sequential scan, full table scan on the table there and pull the results.
‫Now, we have two things.
‫If the book is so that you have fumaroles is going to use an index scan, if you if I thought that is
‫going to have a lot of rows is going to say, you know what, it's way cheaper for me to do a sequential
‫scan on the table because I'm going to go there anyway.
‫I don't want to jump read the index and then read a table that's expensive.
‫So if I'm reading at a table and the index all the time, might as well just go and read the table fully.
‫Right.
‫That's easier.
‫So now that compromise between the two is when you have a case where you don't have a lot of rows,
‫you don't have a lot of rows.
‫So that justifies a full table scan, but you have quality enough that it's actually efficient to use
‫the index.
‫So what this does is actually does a bitmap scan.
‫Let's give an example of a witness.
‫A witness scan is when you do when you do something a little bit slightly less ridiculous, like give
‫me the grades that are greater than ninety five.
‫Right.
‫Like.
‫Course doesn't really know how much, but it knows this a lot, but since there is an index on.
‫Which is the grades it's worth doing an index scan, but doing an index card and jumping to the table
‫all the time for every value I find is expensive.
‫So it's going to do something called the bitmap index.
‫Let's talk about that a little bit.
‫So the bitmap is good index and you're going to see something some some graphics that I put on the video
‫here.
‫Where?
‫Polska is going to build a bitmap and it's basically an array of bits and the values represent the page
‫number, so bit number zero is page number zero, but no one is number one and so on and below that
‫number, total number of pages that is in this relation or this table in this case.
‫OK, so with that, with the Postgres will do it will do a scan, a bitmap scan G and says, you know
‫what, when I find a value that satisfies this condition, I'm going to do an index scan.
‫This is a normal scan.
‫But when I find something, I'm not going to jump directly to the table when I find a page.
‫No, no, no.
‫I'm going to set a bit on that bitmap.
‫So, for example, let's say I found a right and that rule belongs to page number nine.
‫So I'm going to go to that bitmap and sit with number nine as one.
‫That means, hey, by the way, I found a role that and Bajou right on page nine and then does goes
‫goes into all of the index and scans the whole index.
‫You have a beautiful bitmap that you can use to jump once to the heap table and pull all these pages
‫get.
‫So that's that's what we're going to do right here.
‫Now we're going to do a bitmap scan.
‫So we're using the number of pages then I know exactly to fetch.
‫I need to jump to the heap once and all those pages.
‫OK.
‫And when I finish all those pages, that's what every page is going to have one or more.
‫Right.
‫That's how Polska starts things.
‫That's what some of those rules will not satisfy the G greater than nine ninety five criteria so that
‫the Postgres does every check on the condition only to filter out the rows that has been filtered and
‫drops the rows that have been put.
‫In this case, we were lucky that that exact number of rows actually fit exactly in the and the pages.
‫So that's a bitmap index.
‫So this is very, very interesting, guys.
‫So let's spice things up a little bit.
‫So let's spice things up a little bit with a bitmap.
‫And so the beauty of the bitmap index is you can scan the multiple indexes or indices of them from the
‫UK.
‫You can scan multiple indexes, build those Bittner's and them together, and then get one beautiful
‫bitmap and then jump to the heap.
‫Let's take an example.
‫I'm going to do it.
‫Explain where greater is greater than 95 and ideas list then.
‫I don't know.
‫Ten thousand when I do that.
‫Look what happened here.
‫I.D. has an index and she has an index.
‫So what does it do then?
‫An index can a bitmap index can on G and calculated that beautiful bitmap that we talked about.
‫And then another bitmap scan on grades, Primerica, which is the ID field and then had now I have to
‫bitmap what it did it just and then.
‫You know how smart this is, guys, by ending then any page that exists in one hand doesn't exist another.
‫I don't have to visit it because one hundred percent that Raul is not going to satisfy my criteria.
‫This is genius.
‫So all of a sudden, instead of having nine thousand rules and whatever this 20 thousand rows, you
‫only get three hundred ninety four rules.
‫Beautiful.
‫And then once we have this beautiful final thank you, go to that heap, do a bitmap heap, scan this
‫time with this final result and the result, and then go and do a recheck.
‫Why?
‫Because you have to do a recheck because you're pitching some pages, some rows on those pages that
‫you're pitching might not satisfy your criteria.
‫So you're doing a recheck again on those thing that's not so expensive because once you figure page,
‫you get you get those calls for free in memory, hot right in the shared memory, to be specific.
‫All right, guys.
‫So that was April scan, full table scan, sequential scan and scan and bitmap and scan and bitmap.
‫Hebes can help you enjoy this video.
‫I'm going to see on the next one.
‫You guys, the state by.